ACM -- 算法小结（四）KMP(POJ3461)

KMP -- POJ3461解题报告

问题描述：给出字符串P和字符串T，问字符串P在字符串T中出现的次数

Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output
1
3
0

简单KMP应用，代码如下：

 1 //poj3461解题报告
 2 #include<iostream>
 3 using namespace std;
 4 
 5 char T[1000005], P[10005];
 6 int len1, len2;
 7 int next[10005];
 8 
 9 void getnext(char P[])
10 {
11     int i = 0, j = -1;
12     next[0] = -1;
13     while(i < len2)
14     {
15         if(j == -1 || P[i] == P[j])
16         {
17             i ++;
18             j ++;
19             next[i] = j;
20         }
21         else
22             j = next[j];
23     }
24 }
25 
26 int kmp()
27 {
28     int i = 0, j = 0;
29     int count = 0;
30     for(i = 0; i < len1; i ++)
31     {
32         while(j > 0 && T[i] != P[j])
33             j = next[j];
34         if(T[i] == P[j])
35             j++;
36         if(j == len2)
37         {
38             count ++;
39             j = next[j];
40         }
41     }
42     return count;
43 }
44 
45 int main()
46 {
47     int t;
48     while(scanf("%d", &t) != EOF)
49     {
50         for(int i = 1; I <= t; i ++)
51         {
52             scanf("%s%s", P, T);
53             int count = 0;
54             len1 = strlen(T);
55             len2 = strlen(P);
56             getnext(P);
57             int k = kmp();
58             printf("%d
", k);
59         }
60     }
61     return 0;
62 }