hihoCoder #1015 KMP

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 void compute_prefix(const string &pattern, vector<int> &prefix) {
 8     prefix[0] = -1;
 9     size_t i_offset = 1, p_offset = 0;
10     while (i_offset < prefix.size() - 1) {
11         if (p_offset != -1 && pattern[p_offset] != pattern[i_offset])
12             p_offset = prefix[p_offset];
13         else
14             prefix[++i_offset] = ++p_offset;
15     }
16 }
17 int KMP_match(const string &text, const string &pattern, const vector<int> &prefix) {
18     int match_time = 0;
19     size_t t_offset = 0, p_offset = 0;
20     while (t_offset < text.size()) {
21         if (p_offset == -1 || text[t_offset] == pattern[p_offset]) {
22             t_offset++; p_offset++;
23             if (p_offset == pattern.size()) match_time++;
24         }
25         else 
26             p_offset = prefix[p_offset];
27     }
28     return match_time;
29 }
30 int main() {
31     int test_count;
32     cin >> test_count;
33     for (int i = 0; i < test_count; i++) {
34         string pattern, text;
35         cin >> pattern >> text;
36         vector<int> prefix(pattern.size() + 1, 0);
37         compute_prefix(pattern, prefix);
38         cout << KMP_match(text, pattern, prefix) << endl;
39     }
40     return 0;
41 }