KMP算法：洛谷3375
根据我的理解，把next数组改成了fail数组。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1000010;
4 char s1[N],s2[N];
5 int l1,l2,fail[N];
6 void getfail(){
7 fail[0]=fail[1]=0;
8 int k;
9 for(int i=1;i<l2;i++){
10 k=fail[i];
11 while(k&&s2[i]!=s2[k]) k=fail[k];
12 fail[i+1]=s2[k]==s2[i]?k+1:0;
13 }
14 return;
15 }
16 void find(){
17 int p2=0;
18 for(int i=0;i<l1;i++){
19 while(s1[i]!=s2[p2]&&p2) p2=fail[p2];
20 if(s1[i]==s2[p2]) p2++;
21 if(p2==l2) printf("%d\n",i-l2+2);
22 }
23 }
24 int main(){
25 scanf("%s%s",&s1,&s2);
26 l1=strlen(s1),l2=strlen(s2);
27 getfail();find();
28 for(int i=1;i<=l2;i++) printf("%d ",fail[i]);
29 return 0;
30 }
AC自动机：洛谷3808
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1000010;
4 int n,ans;
5 char ss[N];
6 int ch[N][26],v[N],fail[N],last[N],tot;
7 inline void insert(char *s){
8 int l=strlen(s),now=0;
9 for(int i=0;i<l;i++){
10 int nxt=s[i]-'a';
11 if(!ch[now][nxt]) ch[now][nxt]=++tot;
12 now=ch[now][nxt];
13 }
14 v[now]++;
15 return;
16 }
17 inline void build(){
18 queue<int>q;
19 for(int i=0;i<26;i++) if(ch[0][i]) q.push(ch[0][i]);
20 int x;
21 while(!q.empty()){
22 x=q.front();q.pop();
23 for(int i=0;i<26;i++)if(ch[x][i]){
24 int j=fail[x];
25 while(j&&!ch[j][i]) j=fail[j];
26 fail[ch[x][i]]=ch[j][i];
27 last[ch[x][i]]=v[ch[j][i]]?ch[j][i]:last[ch[j][i]];
28 q.push(ch[x][i]);
29 }
30 }
31 return;
32 }
33 inline void find(char* s){
34 int l=strlen(s),now=0;
35 for(int i=0;i<l;i++){
36 int c=s[i]-'a';
37 while(now&&!ch[now][c]) now=fail[now];
38 now=ch[now][c];
39 int j=now;
40 while(j) ans+=v[j],v[j]=0,j=last[j];
41 }
42 return;
43 }
44 int main(){
45 scanf("%d",&n);
46 for(int i=1;i<=n;i++){scanf("%s",ss);insert(ss);}
47 scanf("%s",ss);
48 build();
49 find(ss);
50 printf("%d",ans);
51 return 0;
52 }
upd:
2018.3.14 重打了AC自动机的模板 (原来的好丑。。)