KMP学习

刚才看了（连接）写的翻译，把kmp算法的工作过程讲的很不错，kmp算法的核心是next，next为什么要那么赋值？其实就是前缀和后缀的最大匹配值，用这个值在匹配失败的时候可以跳过一个不必要的匹配。

移动的位数 = 已匹配的字符数 - 对应部分的匹配值（也就是前缀和后缀的最大相等值）。

为什么要这么移动呢？其实仔细想想也是可以明白的，首先必须明白被匹配的串是不会移动的，我们不会回去再重新匹配，所以只能移动模式串，模式前缀和后缀相等的很明显是可以不用在匹配了，比较感性的理解。

这是求next数组的函数

void FindNext(char s[], int next[])

{///因为匹配的时候当前不成功要找寻前面匹配成功的，所以当前保存前面的串，方便操作

    int j=-, i=, len = strlen(s);

    next[] = -;

    while(i < len)

    {

        if(j==- || s[i]==s[j])

            next[++i] = ++j;

        else

            j = next[j];

    }

}

巴特西

KMP学习

最新文章

热门文章