string/z.cpp


1
2
3
4
5
6
7
8
9
10
11

vector<int> Z(const string& s) {
    int n = sz(s);
    vector<int> z(n, n);
    int x = 0, y = 0;
    for (int i = 1; i < n; i++) {
        z[i] = max(0, min(z[i - x], y - i + 1));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            x = i, y = i + z[i], z[i]++;
    }}
    return z;
}