| 1 | int* z_values(const string &s) { |
| 2 | int n = size(s); |
| 3 | int* z = new int[n]; |
| 4 | int l = 0, r = 0; |
| 5 | z[0] = n; |
| 6 | rep(i,1,n) { |
| 7 | z[i] = 0; |
| 8 | if (i > r) { |
| 9 | l = r = i; |
| 10 | while (r < n && s[r - l] == s[r]) r++; |
| 11 | z[i] = r - l; r--; |
| 12 | } else if (z[i - l] < r - i + 1) z[i] = z[i - l]; |
| 13 | else { |
| 14 | l = i; |
| 15 | while (r < n && s[r - l] == s[r]) r++; |
| 16 | z[i] = r - l; r--; } } |
| 17 | return z; } |
| 18 | // vim: cc=60 ts=2 sts=2 sw=2: |