KMP算法实现

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
const int N=1e6+10;
6
int nextt[N]={-1};
7
string s1,s2;
8
void tonext(){
9
  int k=-1;
10
  for(int i=1;i<s2.size();i++){
11
    while(k>-1&&s2[i]!=s2[k+1]) k=nextt[k];
12
    if(s2[i]==s2[k+1]) k++;
13
    nextt[i]=k;
14
  }
15
}
16
void kmp(){
17
  tonext();
18
  int k=-1,len1=s1.size(),len2=s2.size();
19
  for(int i=0;i<len1;i++){
20
    while(k>-1&&s1[i]!=s2[k+1]) k=nextt[k];
21
    if(s1[i]==s2[k+1]) k++;
22
    if(k==len2-1){
23
      cout<<i-len2+2<<endl;
24
    }
25
  }
26
  return;
27
}
28
signed main(){
29
  cin>>s1>>s2;
30
  kmp();
31
    for(int i=0;i<s2.size();i++) cout<<nextt[i]+1<<' ';
32
}