把另一種解法也貼出來吧（由于題目的背景是在大量數據中查找少數關鍵字，效率不如前面的解法）。
基本思路：將 關鍵字 從1開始編號， 對分詞后源詞組，進行映射，如果是關鍵字，就映射為該關鍵字的編號，否則映射為數字0
用兩個指針，一前一后，很容易就可以實現在O(n)時間內找出結果。
1
2 #include<iostream>
3 #include<vector>
4 #include<string>
5 #include<algorithm>
6 #include<set>
7
8 #define USE_CPLUSPLUS0x 1
9
10 #if USE_CPLUSPLUS0x
11 #include<unordered_map>
12 #else
13 #include<map>
14 #endif
15
16 #include<cassert>
17
18 using std::string;
19 using std::vector;
20 using std::cout;
21
22
23 #if USE_CPLUSPLUS0x
24 struct Cmp{
25 bool operator()(const string* a, const string* b) const { return *a == *b; }
26 } ;
27
28 struct Hash{
29 size_t operator()(const string* a) const { return std::hash<string>()(*a);}
30 } ;
31
32 typedef std::unordered_map<const string*, size_t, Hash, Cmp> Dict;
33 #else
34 struct Cmp{
35 bool operator()(const string* sa, const string * sb) const { return *sa < *sb; }
36 } ;
37
38 typedef std::map<const string*, size_t, Cmp> Dict;
39 #endif
40
41 template<typename T>
42 void output(T beg, T end, const char str[] = "", const char sep[] = "")
43 {
44 cout << str;
45 while (beg != end) cout << *beg++ << sep;
46 cout << "\n";
47 }
48
49 //方法一，先掃一遍找出原字符串包含的關鍵詞數，再掃兩遍，找出所求結果
50 void solve(const string str[], const size_t str_sz,
51 const string keyword[], const size_t keyword_sz)
52 {
53 if (str_sz == 0 || keyword_sz == 0) return;
54
55 vector<size_t> old_pos; //分詞后的字符串，在原字符串中的位置
56 old_pos.reserve(str_sz + 1);
57 old_pos.push_back(0);
58 for (size_t i = 0, sum = 0; i < str_sz; ++i) {
59 sum += str[i].size();
60 old_pos.push_back(sum);
61 }
62
63 Dict key_idx; //關鍵字映射為數字，以減少字符串比較
64 for (size_t i = 0; i < keyword_sz; ++i)
65 key_idx.insert(Dict::value_type(&keyword[i], i + 1));
66
67 typedef size_t User_size_type;
68 vector<User_size_type> str_idx(str_sz); //將原字符串映射為數字
69 vector<User_size_type> keyword_count(keyword_sz + 1);
70
71 size_t matched = 0, pos = 0;
72 for (size_t i = 0; i < str_sz; ++i) {
73 Dict::iterator it = key_idx.find(&str[i]);
74 if (it == key_idx.end()) { str_idx[i] = 0; continue; }
75 size_t idx = (str_idx[i] = it->second); //將原字符串映射為數字
76 if (++keyword_count[idx] == 1) { ++matched; pos = idx;}
77 }
78
79 size_t beg = 0, end = 0, len = -1; //記錄結果
80 if (matched > 0) {
81 std::fill(keyword_count.begin(), keyword_count.end(), 0);
82 for (size_t high = 0; high < pos; ++high) ++keyword_count[str_idx[high]] ;
83 for (size_t high = pos, low = 0; high < str_sz; ++high) {
84 size_t idx = str_idx[high]; //將原字符串映射為數字
85 if (idx == 0) continue;
86 ++keyword_count[idx];
87 for (; ;++low) {
88 size_t idx = str_idx[low];
89 if (idx == 0) continue;
90 assert(idx <= keyword_sz);
91 if (keyword_count[idx] == 1) break;
92 --keyword_count[idx];
93 }
94 size_t plen = old_pos[high] - old_pos[low];
95 if (plen < len) { len = plen; beg = low; end = high + 1; }
96 }
97 }
98
99 output(&str[0], &str[str_sz], "words: ");
100 output(&keyword[0], &keyword[keyword_sz], "keywords: ", " ");
101 if (matched > 0 && matched < keyword_sz)
102 cout << "(" << matched << "/" << keyword_sz << " Matched) ";
103 output(&str[beg], &str[end], "result: ");
104 cout << "\n";
105 }
106
107
108 //方法二，先掃兩遍嘗試找出結果，若原字符串沒有包含所有關鍵詞，則再掃兩遍
109 void solve2(const string str[], const size_t str_sz,
110 const string keyword[], const size_t keyword_sz)
111 {
112 if (str_sz == 0 || keyword_sz == 0) return;
113
114 vector<size_t> old_pos; //分詞后的字符串，在原字符串中的位置
115 old_pos.reserve(str_sz + 1);
116 old_pos.push_back(0);
117 for (size_t i = 0, sum = 0; i < str_sz; ++i) {
118 sum += str[i].size();
119 old_pos.push_back(sum);
120 }
121
122 Dict key_idx; //關鍵字映射為數字，以減少字符串比較
123 for (size_t i = 0; i < keyword_sz; ++i)
124 key_idx.insert(Dict::value_type(&keyword[i], i + 1));
125
126 typedef size_t User_size_type;
127 vector<User_size_type> str_idx(str_sz); //將原字符串映射為數字
128 vector<User_size_type> keyword_count(keyword_sz + 1);
129
130 size_t unmatched = keyword_sz, pos = 0;
131 size_t beg = 0, end = 0, len = -1; //記錄結果
132 for (size_t high = 0, low = 0; high < str_sz; ++high) {
133 Dict::iterator it = key_idx.find(&str[high]);
134 if (it == key_idx.end()) { str_idx[high] = 0; continue; }
135 size_t idx = (str_idx[high] = it->second); //將原字符串映射為數字
136
137 if (++keyword_count[idx] == 1) { --unmatched; pos = high; }
138
139 if (unmatched == 0) {
140 for (; ;++low) {
141 size_t k = str_idx[low];
142 if (k == 0) continue;
143 assert(k <= keyword_sz);
144 if (keyword_count[k] == 1) break;
145 --keyword_count[k];
146 }
147 size_t plen = old_pos[high] - old_pos[low];
148 if (plen < len) { len = plen; beg = low; end = high + 1; }
149 }
150 }
151
152 size_t matched = keyword_sz - unmatched;
153 if (matched != 0 && matched < keyword_sz) { //沒找到所有關鍵字
154 std::fill(keyword_count.begin(), keyword_count.end(), 0);
155 for (size_t high = 0; high < pos; ++high) ++keyword_count[str_idx[high]] ;
156 for (size_t high = pos, low = 0; high < str_sz; ++high) {
157 size_t idx = str_idx[high]; //將原字符串映射為數字
158 if (idx == 0) continue;
159 ++keyword_count[idx];
160 for (; ;++low) {
161 size_t idx = str_idx[low];
162 if (idx == 0) continue;
163 assert(idx <= keyword_sz);
164 if (keyword_count[idx] == 1) break;
165 --keyword_count[idx];
166 }
167 size_t plen = old_pos[high] - old_pos[low];
168 if (plen < len) { len = plen; beg = low; end = high + 1; }
169 }
170 }
171
172 output(&str[0], &str[str_sz], "words: ");
173 output(&keyword[0], &keyword[keyword_sz], "keywords: ", " ");
174 if (matched > 0 && matched < keyword_sz)
175 cout << "(" << matched << "/" << keyword_sz << " Matched) ";
176 output(&str[beg], &str[end], "result: ");
177 cout << "\n";
178 }
179
180
181 template<typename T, size_t sz>
182 inline size_t getsz(T (&)[sz]) { return sz; }
183
184 int main()
185 {
186 string keyword[] = { "微軟", "計算機", "亞洲", "中國"};
187 string str[] = {
188 "微軟","亞洲","研究院","成立","于","1998","年","，","我們","的","使命",
189 "是","使","未來","的","計算機","能夠","看","、","聽","、","學","，",
190 "能","用","自然語言","與","人類","進行","交流","。","在","此","基礎","上",
191 "，","微軟","亞洲","研究院","還","將","促進","計算機","在","亞太","地區",
192 "的","普及","，","改善","亞太","用戶","的","計算","體驗","。","”"
193 };
194 solve(str, getsz(str), keyword, getsz(keyword));
195 std::cout << "\n";
196 solve2(str, getsz(str), keyword, getsz(keyword));
197 }
198
199