kmp板子

主串a，模式串b，求b在a中出现的位置

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 const int N=1e6+4;
int la,lb;
int f[N],p[N];
 char a[N],b[N];
 
 void solve(){
     int i,j; la=strlen(a+1),lb=strlen(b+1);
     
     p[1]=0; j=0;
     for(i=2;i<=lb;i++){
         while(j>0&&b[i]!=b[j+1]) j=p[j];
         if(b[i]==b[j+1]) j++;
         p[i]=j;
     }
    
    j=0;
     for(i=1;i<=la;i++){
         while(j>0&&a[i]!=b[j+1]) j=p[j];
         if(a[i]==b[j+1]) j++;
         f[i]=j;
         
         if(f[i]==lb) cout<<i-lb+1<<'\n';
     }
 }
 signed main(){
     cin>>a+1>>b+1; solve();
     for(int i=1;i<=lb;i++) cout<<p[i]<<' ';
 }