思路

显然endpos的大小就对应了对应子串的出现次数，所以快速求出endpos的大小，然后用它更新对应子串长度（minlen[i]~maxlen[i]）的答案即可

endpos的大小可以拓扑排序求出，发现suflink构成了一棵树，每个点代表的串都是孩子的后缀，所以$$endpos[x]\ge\sum_{v\in son[x]}endpos[v]$$

至于为什么会大于呢，因为这个节点有可能还能接受s的一个前缀，这个子串无法从孩子处转移来，但是容易发现，只有增加的节点能接受一个前缀，分裂的节点不行，所以拓扑排序就能求出endpos的大小了

更新答案时，因为从1到n，ans不上升，所以可以每个state更新maxlen的答案，最后再倒序扫一遍

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

const int MAXN = 1000100*2;

int trans[MAXN][26],suflink[MAXN],ispre[MAXN],maxlen[MAXN],minlen[MAXN],cnt,in[MAXN],ans[MAXN],n,endpos[MAXN];

char s[MAXN];

int new_st(int _maxlen,int _minlen,int *_trans,int _suflink){

    ++cnt;

    maxlen[cnt]=_maxlen;

    minlen[cnt]=_minlen;

    if(_trans)

        for(int i=0;i<26;i++)

            trans[cnt][i]=_trans[i];

    suflink[cnt]=_suflink;

    return cnt;

}

int add_len(int u,int c){

    int z=new_st(maxlen[u]+1,0,NULL,0);

    ispre[z]=true;

    while(u&&(!trans[u][c])){

        trans[u][c]=z;

        u=suflink[u];

    }

    if(!u){

        suflink[z]=1;

        minlen[z]=1;

        return z;

    }

    int v=trans[u][c];

    if(maxlen[v]==maxlen[u]+1){

        minlen[z]=maxlen[v]+1;

        suflink[z]=v;

        return z;

    }

    int y=new_st(maxlen[u]+1,0,trans[v],suflink[v]);

    minlen[v]=minlen[z]=maxlen[y]+1;

    suflink[v]=suflink[z]=y;

    minlen[y]=maxlen[suflink[y]]+1;

    while(u&&trans[u][c]==v){

        trans[u][c]=y;

        u=suflink[u];

    }

    return z;

}

queue<int> q;

int main(){

    scanf("%s",s+1);

    n=strlen(s+1);

    int pre=1;

    cnt=1;

    for(int i=1;i<=n;i++)

        pre=add_len(pre,s[i]-'a');

    for(int i=1;i<=cnt;i++)

        in[suflink[i]]++;

    for(int i=1;i<=cnt;i++)

        if(!in[i])

            q.push(i);

    while(!q.empty()){

        int x=q.front();

        q.pop();

        endpos[x]+=ispre[x];

        endpos[suflink[x]]+=endpos[x];

        in[suflink[x]]--;

        if(!in[suflink[x]])

            q.push(suflink[x]);

    }

    for(int i=1;i<=cnt;i++)

        ans[maxlen[i]]=max(ans[maxlen[i]],endpos[i]);

    for(int i=n-1;i>=1;i--)

        ans[i]=max(ans[i],ans[i+1]);

    for(int i=1;i<=n;i++)

        printf("%d\n",ans[i]);

    return 0;

}