POJ 2752

错误：
1. z-algorithm 实现错误
2. 忘记给z[]清零
3. KMP 更容易
 1 void z_algorithm(char *s, int n) {
 2     int L = 0, R = 0;
 3     for (int i = 1; i < n; ++i) {
 4         if (i > R) {
 5             L = R = i;
 6             while (R < n && s[R - L] == s[R]) ++R;
 7             z[i] = R - L;
 8             --R;
 9         } else {
10             int k = i - L;
11             if (z[k] < R - i + 1)
12                 z[i] = z[k];
13             else {
14                 L = i;
15                 while (R < n && s[R - L] == s[R]) ++R;
16                 z[i] = R - L;
17                 --R;
18             }
19         }
20     }
21 }
22 vector<int> z_function(string s) {
23     int n = (int) s.length();
24     vector<int> z(n);
25     for (int i = 1, l = 0, r = 0; i < n; ++i) {
26         if (i <= r)
27             z[i] = min (r - i + 1, z[i - l]);
28         while (i + z[i] < n && s[z[i]] == s[i + z[i]])
29             ++z[i];
30         if (i + z[i] - 1 > r)
31             l = i, r = i + z[i] - 1;
32     }
33     return z;
34 }
View Code