《Cracking the Coding Interview》——第18章：难题—

《Cracking the Coding Interview》——第18章：难题——题目8

2014-04-29 03:10

题目：给定一个长字符串S和一个词典T，进行多模式匹配，统计S中T单词出现的总个数。

解法：这是要考察面试者能不能写个AC自动机吗？对面试题来说太难了吧？我不会，所以只写了个KMP用N次的方法。

代码：

 1 // 18.8 Given a list of words and a piece of text, find out how many times in total, all words appear in the text.
 2 #include <iostream>
 3 #include <string>
 4 #include <unordered_set>
 5 #include <vector>
 6 using namespace std;
 7 
 8 class Solution {
 9 public:
10     int KMPMatch(const string &word, const string &pattern) {
11         int index;
12         int pos;
13         int result;
14         
15         lw = word.length();
16         lp = pattern.length();
17         calculateNext(pattern);
18 
19         index = pos = 0;
20         result = 0;
21         while (index < lw) {
22             if (pos == -1 || word[index] == pattern[pos]) {
23                 ++index;
24                 ++pos;
25             } else {
26                 pos = next[pos];
27             }
28             
29             if (pos == lp) {
30                 pos = 0;
31                 ++result;
32             }
33         }
34         
35         return result;
36     };
37     
38     ~Solution() {
39         next.clear();
40     };
41 private:
42     int lw;
43     int lp;
44     vector<int> next;
45     
46     void calculateNext(const string &pattern) {
47         int i = 0;
48         int j = -1;
49         
50         next.resize(lp + 1);
51         next[0] = -1;
52         while (i < lp) {
53             if (j == -1 || pattern[i] == pattern[j]) {
54                 ++i;
55                 ++j;
56                 next[i] = j;
57             } else {
58                 j = next[j];
59             }
60         }
61     };
62 };
63 
64 int main()
65 {
66     string text;
67     unordered_set<string> dict;
68     Solution sol;
69     int n, i;
70     int sum;
71     
72     while (cin >> n && n > 0) {
73         for (i = 0; i < n; ++i) {
74             cin >> text;
75             dict.insert(text);
76         }
77         cin >> text;
78         
79         sum = 0;
80         unordered_set<string>::const_iterator usit;
81         for (usit = dict.begin(); usit != dict.end(); ++usit) {
82             sum += sol.KMPMatch(text, *usit);
83         }
84         cout << sum << endl;
85         
86         dict.clear();
87     }
88     
89     return 0;
90 }