// 0-base
// input :  a b c a b a b c a
// output : 9 0 0 2 0 4 0 0 1

vector<int> z_algo(const string &s) {
    int l = 0, r = 0;
    int N = sz(s);
    vector<int> Z(N);
    Z[0] = N;
    repp(i, 1, N) {
        if (i > r) {
            l = r = i;
            while(r < N and s[r] == s[r-l]) r++;
            r--;
            Z[i] = r-l+1;
        } else {
            int k = i-l;
            if (Z[k] < r-i+1) Z[i] = Z[k];
            else {
                l = i;
                while(r < N and s[r] == s[r-l]) r++;
                r--;
                Z[i] = r-l+1;
            }
        }
    }
    return Z;
}