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\n", kmp(s, t)); 44 } 45 return 0; 46 }
