KMP算法(1)

qq1242009750

KMP算法是字符串搜索算法中最高效的算法。
之所以说它高效是因为在目标串中加入了回溯下标，使其在失配时能迅速重新匹配，那接下我们分析一下BF和KMP吧。
BF算法 它在失配的时候目标串会从头开始匹配，而源串则会移动到下一个待匹配的元素上
BF：

BF工作介绍

从上面我们可以得知这样如此的重复匹配导致了时间复杂度增加 O(mXn)   m：源串   n:目标串
而KMP算法呢，正因为有了Next数组，所以在失配时只需要回溯查找就OK啦。
那KMP算法Next是怎样得出来的呢？ 哈哈，其实也很简单，只要记住这句话就可以啦：Next串中前一个目标字符的匹配度决定下一个字符的Next串元素。
KMP：

Kmp

void Get_Next(char *t ,int *next)
{
        int i/*前*/ = 0, j/*后*/ = 1;
        next[1] = 0;
        while (j < t[0])
        {
                if (0 == i || t[i] == t[j])
                {
                        ++i;
                        ++j;
                        next[j] = i;
                }
                else
                {
                        i = next[i];                //回溯工作
                }
        }
}

kMP_Next

从上面的工作图中我们可以看出红色方框倒数第一个元素的Next值完全是由前一个目标串与Next决定的。