max occurrence

#include<bits/stdc++.h>
#define MAX 250007

using namespace std;

struct node{
    int next[26];
    int link, len;
} sa[2*MAX];

int ans[2*MAX], cnt[2*MAX], radix[2*MAX], dir[2*MAX];
int sz, last, n;

char txt[MAX];
void init(){
    sz = 1;
    last = 0;
    sa[0].link = -1;
    sa[0].len = 0;
}

void extends(int c){
    int cur = sz++;
    sa[cur].len = sa[last].len + 1;
    dir[cur] = 1;
    for(; last != -1 && !sa[last].next[c]; last = sa[last].link) sa[last].next[c] = cur;

    if(last == -1) sa[cur].link = 0;
    else{
        int q = sa[last].next[c];
        if(sa[q].len == sa[last].len + 1) sa[cur].link = q;
        else{
            int clone = sz++;
            sa[clone].len = sa[last].len + 1;
            sa[clone].link = sa[q].link;
            memcpy(sa[clone].next, sa[q].next, sizeof sa[q].next);
            for(; last != -1 && sa[last].next[c] == q; last = sa[last].link) sa[last].next[c] = clone;
            sa[cur].link = sa[q].link = clone;
        }
    }
    last = cur;
}

int radixSort(){
    for(int i = 1; i <= sz; i++) cnt[sa[i].len]++;
    for(int i = n; i >= 0; i--) cnt[i] += cnt[i+1];
    for(int i = 1; i <= sz; i++) radix[cnt[sa[i].len]--] = i;
}

int main(){
    scanf("%s", txt);
    n = strlen(txt);
    init(); for(int i = 0; i < n; i++) extends(txt[i]-'a');
    radixSort();
    for(int i = 1; i <= sz; i++){
        int now = radix[i];
        dir[sa[now].link] += dir[now];
        ans[sa[now].len] = max(ans[sa[now].len], dir[now]);
    }
    for(int i = n; i > 0; i--) ans[i] = max(ans[i], ans[i+1]);
    for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}