18.kmp

y总给的模板，🐒记是好记，但模式串和主串的下标都要从1开始处理~

---

原题链接

两个匹配:
一个是模式串与文本串的匹配，还有一个是模式串的自我匹配。

• 求next数组

其中next[i]数组表示的是:子串s[1~i]的最长相等前后缀的前缀最后一位的下标。
例如：图中i=5时，字串ababa的next[5]=3，即aba

next数组的自我匹配

• kmp

模式串与文本串匹配过程完全类似

kmp

• 时间复杂度O(n+m);

//同样分析一个就可
for (i = 1; i < =n; i++ )
{ 
//3. 两个循环的时间复杂度是O(2n),所以KMP的时间复杂度是O(n)
        for( j && s[i] != pattern[j+1] )
       { 
                 j = ne[j] 
//2. 这里j会减值,由于next[j]肯定小于j,所以j最多减n次
        }

        if s[i] == pattern[j+1]
        {
            if (j == m)
                return i - m + 1 
            j++ 
//1. 在循环中,每次循环j最多+1,所以j最多加n次
        }
    }

• 最小循环节

最小循环节

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=1e5+10;
int n,m;
char s[MAX],p[MAX];
int ne[MAX];
int main()
{
    cin>>n>>s+1>>m>>p+1;
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&p[i]!=s[j+1])j=ne[j];
        if(p[i]==s[j+1])
            j++;
        if(j==n)
        {
             cout<<i-n<<" ";
             j=ne[j];
        }
    }
}