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

太过爱你忘了你带给我的痛 2023-06-05 15:57 25阅读 0赞

# #

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;
    }