+我们已经入门了后缀自动机,并且给出了后缀自动机O(n)的构造算法.现在继续前行.hihocoder#:后缀自动机三·重复旋律6
分析时间限制:ms单点时限:ms内存限制:MB描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。输入共一行，包含一个由小写字母构成的字符串S。字符串长度不超过。输出共Length(S)行，每行一个整数，表示答案。样例输入aab样例输出hint长度为1的子串出现次数最多的是a,出现次数是2.长度为2的子串出现次数最多的是aa(当然,不唯一,也可以是ab),出现次数是1长度为3的子串出现次数最多的是aab,出现次数是1所以输出
本题是SAM的运用.通过的学习,我们知道了一个字符串S的后缀自动机其实是一部用于识别S的所有子串的机器,而且通过进一步的学习,我们知道如果一个字符串不是S的子串的话,则将其一个字符一个字符的喂进SAM中的话,则将必定在喂入某个字符的时候出现无路可走的情况（即喂入字符c,trans[c]=null,而不能正确的转移到sam的某个节点去）.换言之,文本串S的后缀自动机是一部恰好只能识别S的全部子串的机器！
那本题该如何求解呢?毫无疑问,先构建S的sam.我们首先断言,如果能求出sam中每个节点的enspos集合的大小,那么此题至少有如下暴力解法.因为我们完全可以写出如下伪代码
FOREACHStatest: FORi=shortest(st)..longest(st): ans[i]=max(ans[i],
endpos(st)
)
其中ans[i]表示出现次数最多的长度为i的子串的出现次数.复杂度是O(N^2)的.至于如何优化,我们后面再说.先至少保证能写出这个暴力算法来.后面再优化复杂度.
那么SAM的每个节点的endpos的大小怎么求出来呢?我们还是以S="aabbabd"为例,它的SAM如下（这个在中已经画过了）
image然后我们将trans去掉,仅仅考虑slink.则我们发现SAM在slink下形成了一棵以起点0为根的树（一定是一棵有根树,因为回想一下中slink是怎么形成的?不就是不断的删掉字符最终删光了走到节点0么?）.
然后各个节点如下
状态子串endposS空串{0,1,2,3,4,5,6,7}1a{1,2,5}2aa{2}3aab{3}4aabb,abb,bb{4}5b{3,4,6}6aabba,abba,bba,ba{5}7aabbab,abbab,bbab,bab{6}8ab{3,6}9aabbabd,abbabd,bbabd,babd,abd,bd,d{7}注意,图2中除了起点0之外,其余的9个顶点被着以两种颜色——一种是浅粉色,一种是绿色.绿色的节点表示是中代码第28行新建的节点z——即S[1,...,i+1]所属的节点（中的附录图1中的z）,换言之是每次新读入字符产生的新的前缀属于的节点.而浅粉色的节点是中代码48行从x拆分出来的y（中的附录图3中的y）,换言之,是拆分出来的节点.也就是S的sam节点的个数=S的长度.多出来的都是拆分出来的节点.例如上图中的5和8就是就是拆分出来的节点.
很明显的事情是,绿色的节点中一定包含前缀,而且前缀就是该节点中最长的那个子串（根据的代码就知道）.而浅粉色节点中一定不包含前缀,因为浅粉色的节点（即中的y）是中的u=S[1,..,i]不断的删除前面的字符走到的节点v然后再读入S[i+1]这个字符产生的节点.既然已经删掉了一些前面的字符,当然不可能是前缀啦~
因为刚刚说了,sam用slink已经形成了一棵有根树.所以我们寻思着能不能构造完毕sam之后,再自底向上递归地将每个顶点的endpos大小求出来.我们想当然的认为父节点的endpos大小恰好等于所有子节点们的endpos大小之和（下面简称这个断言为A）.然鹅,事实上,这是不正确的.
例子1:状态8有两个儿子分别是状态3和状态7（即slink[7]=slink[3]=8)，其中endpos(3)={3},endpos(7)={6}，endpos(8)={3,6},所以
endpos(8)
=
endpos(3)
+
endpos(7)
,没毛病~例子2:状态1有两个儿子分别是状态2和状态6，其中endpos(2)={2},endpos(6)={5}，butendpos(1)={1,2,5}所以
endpos(1)
endpos(2)
+
endpos(6)
所以父节点的enpos大小=子节点们的endpos大小之和并不成立!那是不是我们不能利用上面优美的树形结构了呢?非也,非也,情况事实上没有辣么的糟糕!
结论:对于浅粉色的节点,A是成立的,对于绿色的节点,A是不成立的,而要将A的叙述改成父节点的endpos大小恰好等于所有子节点们的endpos大小之和再加1,而且加的这个1就是父节点中的最长的那个子串————也就是前缀S[1,...,i].
为什么上面的结论对呢?首先根据的引理,我们知道父节点的诸多子节点之间是不可能endpos交非空的.否则这些子节点之间就存在后缀关系,这些子节点之间就会存在slink关系.就不会是兄弟关系了.其次,如果父节点的endpos中存在一个不在任何子节点的endpos中出现的值,假设这个值是q,并且产生这个q的父节点中的子串是sub=S[p,..,q],则如果p1（浅粉色节点）的话,可以想象sub一定会属于某个子节点的!除非p=1（绿色节点）,即产生这个q的是一个前缀!那么根据我们sam的构造算法,就不可能属于任何一个子节点!
这就是为什么我们要区分浅粉色节点和绿色节点的理由!
那么既然是树上的递归,我们还有一个要考虑的问题就是叶子节点的值是多少?我们说,叶子节点的endpos大小一定是1.因为节点就只有浅粉色和绿色两种,而浅粉色节点是拆分出来的节点,根据中的构造算法,浅粉色的节点一定不可能是叶子.所以叶子只可能是绿色节点（简称绿叶）.绿叶一定不可能endpos的大小1,否则说明绿叶中最长的那个子串——即前缀S[1,...,i]出现次数1——即不仅仅在i处出现,还在j处出现,显然ji.那么考虑S[1,..,j]所在的节点.则不难知道此绿叶必定不是叶子节点了.所以叶子的endpos的大小一定是1
至此,我们知道了如何得到每个sam节点中的endpos大小的算法.
构建sam.sam节点中除了sam必须的trans、slink之外，还需要shortest（因为本题和子串长度有关）、longest、endpos（endpos的大小）、flag（是不是绿色节点,true表示是）这4个业务字段.类似于ac自动机构造fail树.构造完sam（或者构造sam途中）之后我们也要使用反向slink构造slink树——一棵以0为根节点的树.即类似于ac自动机和fail树之间的关系是:节点都是那些节点,只是节点组织的形式不一样,ac自动机靠的是trie,而fail树靠的是反向fail指针.后缀自动机和slink树的关系是:节点也都是那些节点,只是节点组织的形式不一样,后缀自动机靠的是trans,而slink树靠的是反向slink指针.slink树的叶子的endpos=1.然后在slink树上递归,求出所有sam节点的endpos字段的值.注意,上面三步的复杂度是O(N)的.而且因为自动机的节点数至多2N个,所以不难知道上面三步算法的常数比较小.是很优秀的.
那么怎么得到答案呢?如果使用本文开头的暴力算法的话,复杂度堕入O(n^2)那岂不是迄今为止slink树的努力全部白费了?非也非也!
对于每个节点,我们不需要去更新节点所有的子串对应长度的答案,也就是我们不需要对每个节点执行下面的O(n)伪代码
FORi=shortest(st)..longest(st): ans[i]=max(ans[i],
endpos(st)
)
只需要更新节点中的longest对应的答案就行了.即对每个节点,只需要执行下面的O(1)伪代码即可
ans[maxlen(st)]=max(ans[maxlen(st)],
endpos(st)
)
然后注意到ans[1],ans[2],...ans[length(S)]一定递减（因为一个长度为i的子串出现了,则长度为i-1、i-2、...、1的子串一定也都出现了）.所以我们只需要继续
FORi=length(S)-1..1:ans[i]=max(ans[i],ans[i+1])
即可。还是以S="aabbabd"为例.我们要求ans[4].那么根据上面的表格,我们知道长为4的子串在4、6、7、9这四个节点中出现过.所以按道理,ans[4]应该在遍历4、6、7、9这4个状态的时候,对于每个状态st,来一次
ans[4]=max(ans[4],endpos(st))
这个过程就是文初的O(n^2)暴力算法.但是其实没必要.因为例如abba这个长度为4的子串在6这个状态出现过.但是它的endpos和longest(6)=aabba是一毛一样的!所以我们只需要得到ans[5]即可.然后用ans[5]来max化ans[4].
综上所述,我们应该使用下面的伪代码来完成对答案的计算
FOREACHStatest:ans[longest(st)]=max(ans[longest(st)],
endpos(st)
)//只更新longest的FORi=length(S)-1..1:ans[i]=max(ans[i],ans[i+1])
上述伪代码的复杂度是O(n)的.
好了,说了这么多,来愉快的切代码吧~
//#include"stdafx.h"#pragma