CPREFIX || Z function

#include <bits/stdc++.h>
#define int long long
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define Task "CPREFIX"
#define READFILE freopen(Task".INP", "r", stdin)
#define WRITEFILE freopen(Task".OUT", "w", stdout)
using namespace std;
typedef vector < int > vi;
string a;
void init(){
    FAST;
    //READFILE;
    //WRITEFILE;
    cin >> a;
}
void sol(){
    int n = a.size();
    a = " " + a;
    vi z(n + 1, 0);
    vi pre(n + 2, 0);
    z[1] = 0;
    for (int k = 2, l = 1, r = 1; k <= n; ++k)
    {
        int x = 0;
        int kk = k - l + 1;
        if (k <= r){
            x = min(z[kk], r - k + 1);
        }
        while (k + x <= n && a[x + 1] == a[k + x]) ++x;
        z[k] = x;
        if (r < k + x - 1){
            r = k + x - 1;
            l = k;
        }
        pre[x]++;
    }
    for (int i = n; i >= 1; --i){
        pre[i] += pre[i + 1];
    }
    for (int i = 1; i <= n; ++i){
        cout << pre[i] + 1 << " ";
    }
}
signed main(){
    init();
    sol();
    return 0;
}