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

• 求next数组

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

• kmp

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

• 最小循环节

  

#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];
        }
    }
}