KMP算法

KMP算法模板题

（选自hiho一下第三周的题目： http://hihocoder.com/contest/hiho3/problem/1）

输入

第一行一个整数N，表示测试数据组数。

接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

输出

对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

样例输入

5

HAHAHA

WQN

ADA

ADADADA

BABABB

BABABABABABABABABB

DAD

ADDAADAADDAAADAAD

样例输出

时间限制:1000ms　　　　单点时限:1000ms　　　　　　　　内存限制:256MB

提交时，CE 提示说数组 next[] 是不合法的 = =，硬生生改成 nxt[]

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 using namespace std;
 7 
 8 const int maxn = 1e4 + 5;
 9 int nxt[maxn];
10 string S, T;
11 
12 void get_next()
13 {
14     int i = 0, j = -1;
15     nxt[0] = -1;
16     while ( i < T.size()) {
17         if (j == -1 || T[i] == T[j]) {  // T[i]:后缀的单个字符； T[j]:前缀的单个字符
18             ++i;
19             ++j;
20             nxt[i] = j;
21         }
22         else j = nxt[j];
23     }
24   //  for (i = 0 ; i < T.size(); i++) {
25   //      printf("next[%d] = %d
", i, next[i]);
26   //  }
27 }
28 
29 int kmp()
30 {
31     get_next();
32     int i = 0, j = 0, Ans = 0;
33     while (i < S.size()) {
34         if (j == -1 || S[i] == T[j]) {
35             ++i;
36             ++j;
37         }
38         else
39             j = nxt[j];       // 指针后退重新开始匹配
40         if (j == T.size()) {   // 匹配
41             Ans++;
42         }
43     }
44     return Ans;
45 }
46 
47 int main()
48 {
49     #ifndef ONLINE_JUDGE
50         freopen("in.txt", "r", stdin);
51     #endif // ONLINE_JUDGE
52 
53     int n;
54     while (scanf("%d", &n) !=EOF) {
55         while (n--) {
56             cin >> T >> S;
57             cout << kmp() << endl;
58         }
59     }
60     return 0;
61 }