「SPOJ8222」Substrings

2014年9月17日6,1097

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


题解

给一个字符串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个

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

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

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

构建实际上很简单。。。

推荐 http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039

 

avatar
3 Comment threads
4 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
两吉Sama丶hzwerhzwer Recent comment authors
  Subscribe  
提醒
两吉Sama丶

万能的黄学长 请告诉我为什么只把主链上的值赋为1而其他的不用管

黄励新

黄学长能不能讲讲后缀自动机 , 感觉网上资料好少……

郭天成

传送门已无效~~