1 int kmpnext[N];
2 char s[N],t[N];///s为主串,t为模式串
3 int slen,tlen;///slen为主串的长度,tlen为模式串的长度
4 inline void getnext()
5 {
6 int i,j;
7 j=kmpnext[0]=-1;
8 i=0;
9 while(i<tlen)
10 {
11 if(j==-1||t[i]==t[j])
12 {
13 kmpnext[++i]=++j;
14 }
15 else
16 {
17 j=kmpnext[j];
18 }
19 }
20 }
21 /*
22 返回模式串T在主串S中首次出现的位置
23 返回的位置是从0开始的。
24 */
25 inline int kmp_index()
26 {
27 int i=0,j=0;
28 getnext();
29 while(i<slen&&j<tlen)
30 {
31 if(j==-1||s[i]==t[j])
32 {
33 i++;
34 j++;
35 }
36 else
37 j=kmpnext[j];
38 }
39 if(j==tlen)
40 return i-tlen;
41 else
42 return -1;
43 }
44 /*
45 返回模式串在主串S中出现的次数
46 */
47 inline int kmp_count()
48 {
49 int ans=0;
50 int i,j=0;
51 if(slen==1&&tlen==1)
52 {
53 if(s[0]==t[0])
54 return 1;
55 else
56 return 0;
57 }
58 getnext();
59 for(i=0;i<slen;i++)
60 {
61 while(j>0&&s[i]!=t[j])
62 j=kmpnext[j];
63 if(s[i]==t[j])
64 j++;
65 if(j==tlen)
66 {
67 ans++;
68 j=kmpnext[j];
69 }
70 }
71 return ans;
72 }