KMP算法(1)
KMP算法是字符串搜索算法中最高效的算法。之所以说它高效是因为在目标串中加入了回溯下标，使其在失配时能迅速重新匹配，那接下我们分析一下BF和KMP吧。
BF算法 它在失配的时候目标串会从头开始匹配，而源串则会移动到下一个待匹配的元素上
BF：
从上面我们可以得知这样如此的重复匹配导致了时间复杂度增加 O(mXn) m：源串 n:目标串
而KMP算法呢，正因为有了Next数组，所以在失配时只需要回溯查找就OK啦。
那KMP算法Next是怎样得出来的呢？ 哈哈，其实也很简单，只要记住这句话就可以啦：Next串中前一个目标字符的匹配度决定下一个字符的Next串元素。
KMP：
void Get_Next(char *t ,int *next)
{
int i/*前*/ = 0, j/*后*/ = 1;
next = 0;
while (j < t)
{
if (0 == i || t == t)
{
++i;
++j;
next = i;
}
else
{
i = next; //回溯工作
}
}
}
从上面的工作图中我们可以看出红色方框倒数第一个元素的Next值完全是由前一个目标串与Next决定的。
页:
[1]