[模板] KMP
被各路奇怪姿势模板洗脑后，决定自己用自己的理解写个模板。
特地用[codevs1204]测了下保证准确性。
时间复杂度：O(n)
1 #include<set>
2 #include<cmath>
3 #include<ctime>
4 #include<queue>
5 #include<stack>
6 #include<cstdio>
7 #include<vector>
8 #include<string>
9 #include<cstring>
10 #include<cstdlib>
11 #include<iostream>
12 #include<algorithm>
13 #define N 1000001
14 using namespace std;
15 int next[N],m,n;
16 char a[N],b[N];
17 inline void get_next(){
18 for(int i=2,j=0;i<=m;i++){
19 while(j&&b[i]!=b[j+1]) j=next[j];
20 j+=(b[i]==b[j+1]);
21 next[i]=j;
22 }
23 }
24 inline void kmp(){
25 for(int i=1,j=0;i<=n;i++){
26 while(j&&a[i]!=b[j+1]) j=next[j];
27 if(a[i]==b[j+1]) j++;
28 if(j==m) printf("%d
",i-m+1);
29 }
30 }
31 inline void init(){
32 scanf("%s%s",a+1,b+1);
33 n=strlen(a+1);
34 m=strlen(b+1);
35 get_next();
36 kmp();
37 }
38 int main(){
39 freopen("kmp.in","r",stdin);
40 freopen("kmp.out","w",stdout);
41 init();
42 fclose(stdin);
43 fclose(stdout);
44 return 0;
45 }