【spoj8222】Substrings

2014年9月17日2,6757

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

 

  • 郭天成2015年6月6日 下午3:25 回复

    传送门已无效~~

    #1  
    • hzwer2015年6月6日 下午6:07 回复
      admin

      baidu都无效了。。没办法

      #11
  • 黄励新2015年12月17日 上午10:19 回复

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

    #2  
    • hzwer2015年12月17日 下午9:22 回复

      上面其实就是我的理解。。。估计要弄懂得找几个ppt看看

      #21
  • 两吉Sama丶2015年12月17日 下午4:04 回复

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

    #3  
    • hzwer2015年12月17日 下午9:22 回复

      主链的每个结点识别一个后缀

      #31
      • 两吉Sama丶2015年12月17日 下午10:58 回复

        您的意思是他们可以到达自动机的最终状态吗?(・_・ヾ

        #32