后缀自动机统计子串长度出现次数 NSUBSTR - Substrings

#

You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.

Input

String S consists of at most 250000 lowercase latin letters.

Output

Output |S| lines. On the i-th line output F(i).

Example

Input:
ababa
Output:
3
2
2
1
1

题意：给你一个字符串，统计每个长度出现的最大次数

思路：给后缀自动机主链每个点赋值为1 ，然后拓补排序，然后更新每个长度，

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5;
struct Node{int ch[26],fa,len;}sam[M];
char s[M];
int n,siz[M],las=1,cnt=1,t[M],sa[M],res[M];
void add(int c){
    int p=las;
    int np=las=++cnt;
    siz[cnt]=1;
    sam[np].len=sam[p].len+1;
    for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
    if(!p)sam[np].fa=1;
    else{
        int q=sam[p].ch[c];
        if(sam[q].len==sam[p].len+1)sam[np].fa=q;
        else{
            int nq=++cnt;
            sam[nq]=sam[q];
            sam[nq].len=sam[p].len+1;
            sam[np].fa=sam[q].fa=nq;
            for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
        }
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) add(s[i]-'a');
    for(int i=1;i<=cnt;i++) t[sam[i].len]++;
    for(int i=1;i<=cnt;i++) t[i]+=t[i-1];
    for(int i=1;i<=cnt;i++) sa[t[sam[i].len]--]=i;
    for(int i=cnt;i;i--){
        siz[sam[sa[i]].fa]+=siz[sa[i]];//使用自己更新父亲
        res[sam[sa[i]].len]=max(res[sam[sa[i]].len],siz[sa[i]]);//更新对应的长度
    }
    for(int i=n-1;i;i--)res[i]=max(res[i+1],res[i]);
    for(int i=1;i<=n;i++)printf("%d\n",res[i]);
    return 0;
}