#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ins insert
#define IOS ios::sync_with_stdio(false);
using namespace std;
const long long MOD = 1000000007;
template<typename T>inline T Bigmod(T base, T power, T MOD){
T ret=1;
while(power)
{
if(power & 1)ret=(ret*base)%MOD;
base=(base*base)%MOD;
power>>=1;
}
return ret;
}
bool sortinrev(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.first > b.first);
}
vector<int>computeLcp(string pat){
int m = pat.size();
vector<int>lcp(m);
lcp[0] = 0;
int len = 0;
int i = 1;
while(i<m)
{
if(pat[len]==pat[i])
{
len++;
lcp[i] = len;
i++;
}
else{
if(len!=0)
{
len = lcp[len-1];
}
else
{
lcp[i] = 0;
i++;
}
}
}
return lcp;
}
int kmp(string txt,string pat)
{
vector<int>lcp=computeLcp(pat);
int n=txt.size(),m = pat.size();
int i = 0,j = 0;
int cnt = 0;
while(i<n)
{
if(pat[j]==txt[i])
{
i++;j++;
}
if(j==m)
{
cnt++;
j = lcp[j-1];
}
else if(i<n && pat[j]!=txt[i])
{
if(j!=0)
{
j = lcp[j-1];
}
else i++;
}
}
return cnt++;
}
int main()
{
IOS
string s,t;
cin>>s;
vector<int>lcp;
lcp=computeLcp(s);
for(int i=0;i<lcp.size();i++)
cout << lcp[i]<<" ";
cout << endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBmMChuKSBmb3IoaW50IGk9MDtpPG47aSsrKQojZGVmaW5lIG1zKHgpIG1lbXNldCh4LDAsc2l6ZW9mKHgpKQojZGVmaW5lIGlucyBpbnNlcnQKI2RlZmluZSBJT1MgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBsb25nIGxvbmcgTU9EID0gMTAwMDAwMDAwNzsKdGVtcGxhdGU8dHlwZW5hbWUgVD5pbmxpbmUgVCBCaWdtb2QoVCBiYXNlLCBUIHBvd2VyLCBUIE1PRCl7CiAgICBUIHJldD0xOwogICAgd2hpbGUocG93ZXIpCiAgICB7CiAgICAgICAgaWYocG93ZXIgJiAxKXJldD0ocmV0KmJhc2UpJU1PRDsKICAgICAgICBiYXNlPShiYXNlKmJhc2UpJU1PRDsKICAgICAgICBwb3dlcj4+PTE7CiAgICB9CiAgICByZXR1cm4gcmV0Owp9Cgpib29sIHNvcnRpbnJldihjb25zdCBwYWlyPGludCxpbnQ+ICZhLAogICAgICAgICAgICAgICBjb25zdCBwYWlyPGludCxpbnQ+ICZiKQp7CiAgICAgICByZXR1cm4gKGEuZmlyc3QgPiBiLmZpcnN0KTsKfQp2ZWN0b3I8aW50PmNvbXB1dGVMY3Aoc3RyaW5nIHBhdCl7CiAgICBpbnQgbSA9IHBhdC5zaXplKCk7CiAgICB2ZWN0b3I8aW50PmxjcChtKTsKICAgIGxjcFswXSA9IDA7CiAgICBpbnQgbGVuID0gMDsKICAgIGludCBpID0gMTsKICAgIHdoaWxlKGk8bSkKICAgIHsKICAgICAgICBpZihwYXRbbGVuXT09cGF0W2ldKQogICAgICAgIHsKICAgICAgICAgICAgbGVuKys7CiAgICAgICAgICAgIGxjcFtpXSA9IGxlbjsKICAgICAgICAgICAgaSsrOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBpZihsZW4hPTApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxlbiA9IGxjcFtsZW4tMV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBsY3BbaV0gPSAwOwogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CgogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBsY3A7Cn0KaW50IGttcChzdHJpbmcgdHh0LHN0cmluZyBwYXQpCnsKICAgIHZlY3RvcjxpbnQ+bGNwPWNvbXB1dGVMY3AocGF0KTsKICAgIGludCBuPXR4dC5zaXplKCksbSA9IHBhdC5zaXplKCk7CiAgICBpbnQgaSA9IDAsaiA9IDA7CiAgICBpbnQgY250ID0gMDsKICAgIHdoaWxlKGk8bikKICAgIHsKICAgICAgICBpZihwYXRbal09PXR4dFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIGkrKztqKys7CiAgICAgICAgfQogICAgICAgIGlmKGo9PW0pCiAgICAgICAgewogICAgICAgICAgICBjbnQrKzsKICAgICAgICAgICAgaiA9IGxjcFtqLTFdOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKGk8biAmJiBwYXRbal0hPXR4dFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIGlmKGohPTApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGogPSBsY3Bbai0xXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlIGkrKzsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gY250Kys7Cn0KaW50IG1haW4oKQp7CglJT1MKICAgIHN0cmluZyBzLHQ7CiAgICBjaW4+PnM7CiAgICB2ZWN0b3I8aW50PmxjcDsKICAgIGxjcD1jb21wdXRlTGNwKHMpOwogICAgZm9yKGludCBpPTA7aTxsY3Auc2l6ZSgpO2krKykKICAgICAgICBjb3V0IDw8IGxjcFtpXTw8IiAiOwogICAgY291dCA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0KCgoK