SPOJ Substrings

题目链接：戳我

题目大意：给定一个字符串，它的长度n<=2e5。求长度1~n的子串出现的最大次数。

对于一个子串，它的出现次数是多少？就是它所在endpos集合的大小qwq（注意，这里的大小不指该endpos里面元素的个数，而是指该endpos类在原串中出现的次数为大小）

那么我们怎么累加endpos的大小呢qwq

对于一个np节点（非分裂节点），初始的siz值为1，但是分裂节点（nq）就是0了。（指叶子节点）

然后我们在parent tree上用拓扑排序从下到上累加（因为每个节点的parent是它的子节点的并集）即可。但是因为每个等价类的longest是递增的，所以我们也完全可以开桶，来根据longest的长度进行排序。

之后对于每一个等价类，我们把答案累加到它的longest上面即可，这样的话后面还可以通过小的继承大的来获得等价类中较短字符串的出现次数qwq

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 2500100
using namespace std;
int n,last=1,tot=1;
int siz[MAXN],c[MAXN],a[MAXN],ans[MAXN],ru[MAXN];
char ch[MAXN];
struct Node{int son[26],ff,len;}t[MAXN<<1];
inline void extend(int c)
{
    int p=last,np=++tot;last=np;
    t[np].len=t[p].len+1;
    while(p&&!t[p].son[c]) t[p].son[c]=np,p=t[p].ff;
    if(!p) t[np].ff=1;
    else
    {
        int q=t[p].son[c];
        if(t[q].len==t[p].len+1) t[np].ff=q;
        else
        {
            int nq=++tot;
            t[nq]=t[q],t[nq].len=t[p].len+1;
            t[np].ff=t[q].ff=nq;
            while(p&&t[p].son[c]==q) t[p].son[c]=nq,p=t[p].ff;
        }
    }
    siz[np]=1;
}
inline void solve()
{
    for(int i=1;i<=tot;i++) c[t[i].len]++;
    for(int i=1;i<=tot;i++) c[i]+=c[i-1];
    for(int i=1;i<=tot;i++) a[c[t[i].len]--]=i;
    for(int i=tot;i>=1;i--)
    {
        int cur=a[i];
        siz[t[cur].ff]+=siz[cur];
        ans[t[cur].len]=max(ans[t[cur].len],siz[cur]);
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%s",ch+1);
    int l=strlen(ch+1);
    for(int i=1;i<=l;++i) extend(ch[i]-'a');
    solve();
    for(int i=l-1;i;--i) ans[i]=max(ans[i],ans[i+1]);
    for(int i=1;i<=l;++i) printf("%d\n",ans[i]);
    return 0;
}

SPOJ Substrings

原文：https://www.cnblogs.com/fengxunling/p/10731927.html