kmp模板：
1 #include <bits/stdc++.h>
2 #define PB push_back
3 #define MP make_pair
4 using namespace std;
5 typedef long long LL;
6 typedef pair<int,int> PII;
7 #define PI acos((double)-1)
8 #define E exp(double(1))
9 #define K 1000000+9
10 int nt[10000+1];
11 char a[K],b[10001];
12 //参数为模板串和next数组
13 //字符串均从下标0开始
14 void kmp_next(char *T,int *nt)
15 {
16 nt[0]=0;
17 for(int i=1,j=0,m=strlen(T);i<m;i++)
18 {
19 while(j&&T[i]!=T[j])j=nt[j-1];
20 if(T[i]==T[j])j++;
21 nt[i]=j;
22 }
23 }
24 int kmp(char *S,char *T,int *nt)
25 {
26 kmp_next(T,nt);
27 int ans=0,sn=strlen(S),tn=strlen(T);
28 for(int i=0,j=0;i<sn;i++)
29 {
30 while(j&&S[i]!=T[j])j=nt[j-1];
31 if(S[i]==T[j])j++;
32 if(j==tn)
33 ans++;
34 }
35 return ans;
36 }
37 int main(void)
38 {
39 int t;cin>>t;
40 while(t--)
41 {
42 scanf("%s%s",b,a);
43 printf("%d\n",kmp(a,b,nt));
44 }
45
46 return 0;
47 }
扩展kmp模板：
1 #include<iostream>
2 #include<string>
3 #include<cstring>
4 #include<cstdio>
5
6 using namespace std;
7 const int K=100005;
8 int nt[K],extand[K];
9 char S[K],T[K];
10 void Getnext(char *T,int *next)
11 {
12 int len=strlen(T),a=0;
13 next[0]=len;
14 while(a<len-1 && T[a]==T[a+1]) a++;
15 next[1]=a;
16 a=1;
17 for(int k=2; k<len; k++)
18 {
19 int p=a+next[a]-1,L=next[k-a];
20 if( (k-1)+L >= p)
21 {
22 int j = (p-k+1)>0 ? (p-k+1) : 0;
23 while(k+j<len && T[k+j]==T[j]) j++;
24 next[k]=j;
25 a=k;
26 }
27 else
28 next[k]=L;
29 }
30 }
31 void GetExtand(char *S,char *T,int *next)
32 {
33 Getnext(T,next);
34 int slen=strlen(S),tlen=strlen(T),a=0;
35 int MinLen = slen < tlen ? slen : tlen;
36 while(a<MinLen && S[a]==T[a]) a++;
37 extand[0]=a;
38 a=0;
39 for(int k=1; k<slen; k++)
40 {
41 int p=a+extand[a]-1, L=next[k-a];
42 if( (k-1)+L >= p)
43 {
44 int j= (p-k+1) > 0 ? (p-k+1) : 0;
45 while(k+j<slen && j<tlen && S[k+j]==T[j]) j++;
46 extand[k]=j;
47 a=k;
48 }
49 else
50 extand[k]=L;
51 }
52 }
53 int main(void)
54 {
55 while(scanf("%s%s",S,T)==2)
56 {
57 GetExtand(S,T,nt);
58 for(int i=0; i<strlen(T); i++)
59 printf("%d ",nt[i]);
60 puts("");
61 for(int i=0; i<strlen(S); i++)
62 printf("%d ",extand[i]);
63 puts("");
64 }
65 return 0;
66 }