Z Algorithm
| 38 | |
| 39 | // Z Algorithm |
| 40 | vector<int> z_function(string s) { |
| 41 | int n = (int) s.length(); |
| 42 | vector<int> z(n); |
| 43 | for (int i=1, l=0, r=0; i<n; ++i) { |
| 44 | if (i <= r) |
| 45 | z[i] = min (r-i+1, z[i-l]); |
| 46 | while (i+z[i] < n && s[z[i]] == s[i+z[i]]) |
| 47 | ++z[i]; |
| 48 | if (i+z[i]-1 > r) |
| 49 | l = i, r = i+z[i]-1; |
| 50 | } |
| 51 | return z; |
| 52 | } |
| 53 | |
| 54 | // KMP LCP Array |
| 55 | vector<int> prefix_function(string s) { |