SPOJ 8222 [后缀自动机]

题目

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|.

输入

String S consists of at most 250000 lowercase latin letters.

输出

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

样例输入

ababa

样例输出

3 2 2 1 1

分析

没什么好分析的hh,基本裸的后缀自动机,对parent树进行Tsort(),自底向上维护r[i]的大小,注意开始赋值时每个实节点(即np,而非nq)的r赋为1,其他为0

完整代码

#include<bits/stdc++.h> #define maxn 500010 //#define DEBUG using namespace std; int n; int sum[maxn],tmp[maxn],f[maxn]; char ch[maxn]; struct SAM { int root,tot,last; int son[maxn][26],fa[maxn],maxl[maxn],r[maxn]; int addnode(int n) {return maxl[++tot]=n,tot;} void init() { root=tot=last=1; memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); memset(maxl,0,sizeof(maxl)); memset(r,0,sizeof(r)); } void add(int pos) { int x=ch[pos]-'a',np=addnode(pos),p=last; last=np,r[np]=1; for( ; p&&!son[p][x] ; p=fa[p] ) son[p][x]=np; if(!p) fa[np]=root; else { int q=son[p][x]; if(maxl[q]==maxl[p]+1) fa[np]=q; else { int nq=addnode(maxl[p]+1); memcpy(son[nq],son[q],sizeof(son[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; for( ; son[p][x]==q ; p=fa[p] ) son[p][x]=nq; } } } void Tsort() { for(int i=1;i<=tot;++i) sum[maxl[i]]++; for(int i=1;i<=n;++i) sum[i]+=sum[i-1]; for(int i=1;i<=tot;++i) tmp[sum[maxl[i]]--]=i; #ifdef DEBUG for(int i=1;i<=tot;++i) printf(" tmp[%d]=%d maxl[tmp[%d]]=%d\n",i,tmp[i],i,maxl[tmp[i]]); #endif } void build() { init(); scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;++i) add(i); Tsort(); } void work() { build(); #ifdef DEBUG for(int i=1;i<=tot;++i) cerr<<"r["<<i<<"]="<<r[i]<<endl; #endif for(int i=tot;i;i--) r[fa[tmp[i]]]+=r[tmp[i]]; for(int i=1;i<=tot;++i) f[maxl[i]]=max(f[maxl[i]],r[i]); for(int i=1;i<=n;++i) printf("%d\n",f[i]); } } sam ; int main() { sam.work(); return 0; } /* Input: ababanoi Output: 3 2 2 1 1 */