題目鏈接：http://poj.org/problem?id=3461
剛剛學(xué)會(huì)KMP，紀(jì)念下
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 char W[100010], T[1000010];
9 int P[100010], lw, lt, ans;
10 void init(){
11 int j = 0;
12 memset(P, 0, sizeof(P));
13 for (int i = 1; i < lw; i++){
14 while (j > 0 && W[j] != W[i]) j = P[j];
15 if (W[j] == W[i]) j += 1;
16 P[i + 1] = j;
17 }
18 }
19 void kmp(){
20 int j = 0;
21 for (int i = 0; i < lt; i++){
22 while (j > 0 && W[j] != T[i]) j = P[j];
23 if (W[j] == T[i]) j += 1;
24 if (j == lw){
25 ans += 1;
26 j = P[j];
27 }
28 }
29 }
30 int main(){
31 int n;
32 while (~scanf("%d", &n)){
33 while (n--){
34 scanf("%s%s", W, T);
35 lw = strlen(W); lt = strlen(T);
36 init();
37 ans = 0;
38 kmp();
39 printf("%d\n", ans);
40 }
41 }
42 return 0;
43