这里分享下我学习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数组就是计算某个坐标之前的字符串的能匹配的前缀与后缀的长度
本质上就是自己和自己的匹配