SPOJ bsubstr
题目大意：给你一个长度为n的字符串，求出所有不同长度的字符串出现的最大次数。
n<=250000
如：abaaa
输出：
4
2
1
1
1
spoj上的时限卡的太严，必须使用O(N)的算法那才能过掉，所以采用后缀自动机解决。
一个字符串出现的次数，即为后缀自动机中该字符串对应的节点的right集合的大小，right集合的大小等于子树中叶子节点的数目。
令dp[i]表示长度为i的字符串出现的最大次数。dp[i]可以通过在后缀链接树中从叶子节点到根节点依次求出。
最后，按长度从大到小，用dp[i]去更新dp[i-1]。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; #define MAXN 250005 #define MAXC 26 struct node { int go[MAXC],sufflink,step,right; void clear() {memset(go,0,sizeof go); sufflink=step=right=0; } }tree[MAXN<<1]; int dp[MAXN],cnt[MAXN],rk[MAXN<<1],root,tot,cur,last,len,ans; char s[MAXN]; void insert(int val) { int p,q; tree[last].go[val]=++tot; cur=tot; tree[cur].clear(); tree[cur].step=tree[last].step+1; tree[cur].right++; for(p=tree[last].sufflink;p&&tree[p].go[val]==0;p=tree[p].sufflink) tree[p].go[val]=cur; if(p==0) tree[cur].sufflink=root; else { q=tree[p].go[val]; if(tree[p].step+1==tree[q].step) tree[cur].sufflink=q; else { tree[++tot].clear(); tree[tot]=tree[q]; tree[tot].right=0; tree[tot].step=tree[p].step+1; tree[cur].sufflink=tree[q].sufflink=tot; for(;tree[p].go[val]==q;p=tree[p].sufflink) tree[p].go[val]=tot; } } last=cur; } void calc() { int temp; for(int i=1;i<=tot;i++)cnt[tree[i].step]++; for(int i=1;i<=len;i++)cnt[i]+=cnt[i-1]; for(int i=1;i<=tot;i++)rk[cnt[tree[i].step]--]=i; for(int i=tot;i>1;i--) { temp=tree[rk[i]].sufflink; if(tree[rk[i]].right>dp[tree[rk[i]].step])dp[tree[rk[i]].step]=tree[rk[i]].right; if(temp)tree[temp].right+=tree[rk[i]].right; } for(int i=len-1;i>=1;i--) if(dp[i+1]>dp[i])dp[i]=dp[i+1]; for(int i=1;i<=len;i++) printf("%d ",dp[i]); } int main() { while(~scanf("%s",s)) { root=last=cur=tot=1; tree[1].clear(); memset(dp,0,sizeof dp); memset(cnt,0,sizeof cnt); len=strlen(s); for(int i=0;i<len;i++) insert(s[i]-'a'); calc(); } return 0;