重铸华农荣光 我辈义不容辞

the ninty day - KMP

这fucking代码，看评论区就是用得少、容易忘，像一粒老鼠屎，还好csp认证可以带纸质资料入场/吃糖

#include<iostream>
using namespace std;
const int N=1000010,M=100010;
char s[N],p[M];
int ne[M];
int n,m,count;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>p+1>>n>>s+1;

    for(int i=2,j=0;i<=m;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];
        if(s[i]==p[j+1]) j++;
        if(j==m){
            j=ne[j];
            cout<<i-m<<" ";
        }
    }

    return 0;
}