diff options
Diffstat (limited to 'string/z.cpp')
| -rw-r--r-- | string/z.cpp | 15 |
1 files changed, 15 insertions, 0 deletions
diff --git a/string/z.cpp b/string/z.cpp new file mode 100644 index 0000000..dbd5ce5 --- /dev/null +++ b/string/z.cpp @@ -0,0 +1,15 @@ +vector<int> Z(const vector<int> &s) { + int n = sz(s); + vector<int> z(n, n); + int l = 0, r = 0, p, q; + for (int i = 1; i < n; ++i) { + if (i <= r && z[i - l] < r - i + 1) { + z[i] = z[i - l]; + } else { + if (i > r) p = 0, q = i; + else p = r - i + 1, q = r + 1; + while (q < n && s[p] == s[q]) ++p, ++q; + z[i] = q - i, l = i, r = q - 1; + }} + return z; +} |