SPOJbsubstr

题目大意：给你一个长度为n的字符串，求出所有不同长度的字符串出现的最大次数。

n =250000

如：ab#

输出：

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,,sizeof go);
sufflink=step=right=;
}
}tree[MAXN ];
int dp[MAXN],cnt[MAXN],rk[MAXN ],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+;
tree[cur].right++;
for(p=tree[last].sufflink;p tree[p].go[val]==;p=tree[p].sufflink)
tree[p].go[val]=cur;
if(p==)
tree[cur].sufflink=root;
else
{
q=tree[p].go[val];
if(tree[p].step+==tree[q].step)
tree[cur].sufflink=q;
else
{
tree[++tot].clear();
tree[tot]=tree[q];
tree[tot].right=;
tree[tot].step=tree[p].step+;
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=;i =tot;i++)cnt[tree[i].step]++;
for(int i=;i =len;i++)cnt[i]+=cnt[i-];
for(int i=;i =tot;i++)rk[cnt[tree[i].step]--]=i;
for(int i=tot;i 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-;i i--)
if(dp[i+] dp[i])dp[i]=dp[i+];
for(int i=;i =len;i++)
printf("%d\n",dp[i]);
}
int main()
{
while(~scanf("%s",s))
{
root=last=cur=tot=;
tree[].clear();
memset(dp,,sizeof dp);
memset(cnt,,sizeof cnt);
len=strlen(s);
for(int i=;i i++)
insert(s[i]-'a');
calc();
}
return ;