KMP模板

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e6+9;
string t,s;
int Next[maxn];

void get_next()
{
    int len = s.length();
    int k=-1 , j = 0;
    Next[0] = -1;
    while(j<len)
    {
        if(k==-1||s[j]==s[k])
        {
            j++,k++;
            // if(s[j]!=s[k])
            Next[j] = k;
            // else Next[j] = Next[k];
        }
        else k = Next[k];
    }
}

void match()
{
    int slen = s.length();
    int tlen = t.length();
    int j = 0,k = 0;
    while(j<tlen)    
    {
        if(k==-1||s[k]==t[j])
        {
            j++,k++;    
        }
        else k = Next[k];
        if(k==slen)
        {
            printf("%d\n",j-k+1);
            k = 0;j--;
        }
    }
}
int main(){
    cin>>t>>s;
    get_next();
    match();
    // cout<<"))"<<endl;
    int llen = s.length();
    // Next[0] = 0;
    for(int i=1;i<=llen;i++)
        printf("%d%c",Next[i]," \n"[i==llen]);
    return 0;
}