「SPOJ8222」Substrings

2014年9月17日6,3697

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

<strong>Input:</strong>
ababa

<strong>Output:</strong>
3
2
2
1
1

<strong>Input:</strong>

ababa

<strong>Output:</strong>

题解

给一个字符串S，令F(x)表示S的所有长度为x的子串中，出现次数的最大值。

求F(1)..F(Length(S)) Length(S) <= 250000

我们构造S的后缀自动机(SAM)，那么对于一个节点s，它的长度范围是[Min(s),Max(s)]，同时他的出现次数是|Right(s)|。

那么我们用 |Right(s)|去更新F(Max(s))的值。同时最后从大到小依次用F(i)去更新F(i-1)即可。

对于SAM，我口胡几句吧

自动机每个结点信息是一个right集合

比如串aaabbaaabd

aaab在其中1-4 6-9出现

则自动机在读入aaab到达的结点是{4,9}

aab和ab也应该到达这个结点，因为他们出现的结尾也是{4,9}

而b是{4,5,9}不到达这个结点

显然，对于一个状态s，若长度l<=r所对应的al，ar满足

ST(al)=ST(ar)=s那么对于任意的l<=x<=r，ST(ax)=s

不妨设s所有合法集合为[Min(s),Max(s)]

al指的是串a的前l个

显然节点信息是集合包含关系

随着串长增加就是集合元素减少

构建自动机的目标就是让所有包含关系变为一棵树

构建实际上很简单。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 500005
#define ll long long
using namespace std;
char s[N];
int S,cnt,last;
int a[N],b[N],f[N],t[N],fa[N],l[N],r[N],ch[N][26];
void add(int x)
{
	int c=a[x];
	int p=last,np=++cnt;last=np;
	l[np]=x;
	for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
	if(!p)fa[np]=S;
	else 
	{
		int q=ch[p][c];
		if(l[p]+1==l[q])fa[np]=q;
		else 
		{
			int nq=++cnt;l[nq]=l[p]+1;
			memcpy(ch[nq],ch[q],sizeof ch[q]);
			fa[nq]=fa[q];
			fa[np]=fa[q]=nq;
			for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
		}
	}
}
int main()
{
	scanf("%s",s+1);
	last=S=++cnt;
	int len=strlen(s+1);
	for(int i=1;i<=len;i++)a[i]=s[i]-'a';
	for(int i=1;i<=len;i++)add(i);
	for(int i=1,p=S;i<=len;i++)
	{
		p=ch[p][a[i]];r[p]++;
	}
	for(int i=1;i<=cnt;i++)b[l[i]]++;
	for(int i=1;i<=len;i++)b[i]+=b[i-1];
	for(int i=1;i<=cnt;i++)t[b[l[i]]--]=i;
	for(int i=cnt;i;i--)r[fa[t[i]]]+=r[t[i]];
	for(int i=1;i<=cnt;i++)f[l[i]]=max(f[l[i]],r[i]);
	for(int i=len;i;i--)f[i]=max(f[i+1],f[i]);
	for(int i=1;i<=len;i++)printf("%d\n",f[i]);
	return 0;
}