[hihoCoder] KMP算法

Each time we find a match, increase the global counter by 1.

For KMP, algorithm, you may refer to the following links which have nice explanations.

KMP on jBoxer's blog;
KMP on geeksforgeeks, with a well-commented C code.

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 vector<int> kmpProcess(string t) {
 8     int n = t.length();
 9     vector<int> lps(n, 0);
10     for (int i = 1, len = 0; i < n; ) {
11         if (t[i] == t[len])
12             lps[i++] = ++len;
13         else if (len) len = lps[len - 1];
14         else lps[i++] = 0;
15     }
16     return lps;
17 }
18 
19 int kmp(string s, string t) {
20     int m = s.length(), n = t.length(), cnts = 0;
21     vector<int> lps = kmpProcess(t);
22     for (int i = 0, j = 0; i < m; ) {
23         if (s[i] == t[j]) {
24             i++;
25             j++;
26         }
27         if (j == n) cnts++;
28         if (i < m && s[i] != t[j]) {
29             if (j) j = lps[j - 1];
30             else i++;
31         }
32     }
33     return cnts;
34 }
35 
36 int main(void) {
37     int cases;
38     scanf("%d", &cases);
39     for (int i = 0; i < cases; i++) {
40         string s, t;
41         cin >> t;
42         cin >> s;
43         printf("%d
", kmp(s, t));
44     }
45     return 0;
46 }