- 2022tysc0158 的博客
【模板】KMP
- 2024-4-6 16:42:35 @
#include<iostream>
#include<string>
using namespace std;
int kmp[100001],p;
string s1,s2;
int main(){
cin>>s1>>s2;
int siz1=s1.size(),siz2=s2.size();
for(int i=2;i<=siz2;i++){
while(p&&s2[i-1]!=s2[p])p=kmp[p];
if(s2[i-1]==s2[p])p++;
kmp[i]=p;
}
p=0;
for(int i=1;i<=siz1;i++){
while(p&&s2[p]!=s1[i-1])p=kmp[p];
if(s2[p]==s1[i-1])p++;
if(p==siz2)cout<<i-siz2+1<<"\n",p=kmp[p];
}
for(int i=1;i<=siz2;i++)cout<<kmp[i]<<" ";
}