kmp字符串

核心概念：最长公共前缀子和
推荐的博客：https://www.cnblogs.com/yjiyjige/p/3263858.html

next数组：

next[i] = j，即模式串的前i个字符组成的字符串中，最长前缀公共子串的长度为j。

for(int i=2,j=0;i<=n;i++)
    {
        
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i] ==p[j+1])j++;
        ne[i] = j;
    }

匹配字符串

for(int i = 1, j = 0; i <= n; i++)
{
    while(j && s[i] != p[j+1]) j = ne[j];
    //如果j有对应p串的元素， 且s[i] != p[j+1], 则失配， 移动p串
    //用while是由于移动后可能仍然失配，所以要继续移动直到匹配或整个p串移到后面（j = 0)

    if(s[i] == p[j+1]) j++;
    //当前元素匹配，j移向p串下一位
    if(j == m)
    {
        //匹配成功，进行相关操作
        j = next[j];  //继续匹配下一个子串
    }
}

Kmp

原文：https://www.cnblogs.com/xinyi-Conan/p/15176455.html