1 // 根据算法引论一书中的说明写的程序
2 #include <stdio.h>
3 #include <string>
4 #define MAX_N 1000
5 using std::string;
6
7 int next[MAX_N];
8
9 void generate_next(const string& pattern) {
10 next[0] = -1;
11 for(int i = 1; i < pattern.length(); ++i) {
12 int j = next[i-1];
13 while (j >= 0 && pattern[j] != pattern[i-1])
14 j = next[j];
15
16 // either pattern[j] == pattern[i-1] or j < 0
17 next[i] = ++j;
18 }
19 }
20
21 void match(const string& text, const string& pattern) {
22
23 generate_next(pattern);
24 for(int i = 0, j = 0; i < text.length(); ++i) {
25 while (j >= 0 && text[i] != pattern[j]) {
26 j = next[j];
27 }
28 // either text[i] = pattern[j] or j = -1
29 ++j;
30 if (pattern.length() == j) {
31 // get a match, this match starts from k in text
32 int k = i - j + 1;
33 printf("%s\n", text.substr(k).c_str());
34 // let j = 0 for next match
35 j = 0;
36 }
37 }
38 }
39
40 int main() {
41 string t = "xyxxyxyxyyxyxyxyyxyxyxx", p = "xy";
42 match(t, p);
43 }
