在另一个'字符串'中搜索子'字符串'

Question

我如何编写一个有效的算法来搜索C中另一个数组中的整数子集数组？例如:

unsigned a[] = {42, 72, 61, 1023, 84, 42, 42, 193, 302, 72};
unsigned long al = 10;
unsigned b[] = {61, 1023, 84};
unsigned long bl = 3;

我已经尝试了一种蛮力的方法,通过循环a然后循环,b如果a[n]是b[0],但如果匹配失败中途然后回溯.这似乎是我能想到的最好的,但我确信必须有更快的方法.

Answer 1

有几种众所周知的高效字符串搜索算法,它们都可以用于此目的.如果子序列是您正在寻找的,那么整数数组和整数数组之间实际上没有区别,每个整数都被分配给字符表示.

如果你的问题真的像你发布的那么小,那么除了蛮力之外,它可能不值得使用任何东西,但我认为这只是你想要做的一个玩具示例.