kmp算法

题目在这~
思路就是求出最小模板链的移动，求出模板链最大的相等前后缀字符串。

#include<iostream>
using namespace std;
const int N=1000010;
char p[N],s[N];
int ne[N];
int main()
{
   
    int n;
    int m;
    scanf("%d",&n);
    cin>>p+1;//注意下标从1开始
    cin>>m;
    cin>>s+1;
    for(int i=2,j=0;i<=n;i++)//i不用从1开始因为ne[1]=0
    {
   
        while(j&&p[j+1]!=p[i])  j=ne[j];//j为0进不了循环
        if(p[j+1]==p[i])    j++;//如果成功了j++
        ne[i]=j;		//记录当前i的ne值
    }
    for(int i=1,j=0;i<=m;i++)
    {
   
        while(j&&p[j+1]!=s[i])  j=ne[j];
        if(p[j+1]==s[i])    j++;
        if(j==n)
        {
   
            j=ne[j];
            cout<<i-n<<' ';
        }
    }
    return 0;
}