字符串比较 kmp算法

这里分享下我学习KMP的心得

假设已经得到next数组，使用数组进行字符串匹配的流程如上代码如下

const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
{

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            //ok  得到答案
            return 0;
        }
    }
}

//==================================================================
下面我们来进行next数组的计算
Next数组就是计算某个坐标之前的字符串的能匹配的前缀与后缀的长度
本质上就是自己和自己的匹配

我的视频题解空间

字符串比较 kmp算法

原文：https://www.cnblogs.com/itdef/p/15312219.html