题目大意:给一个字符串S,再给一个字符串T,设T的长度为len,问T的循环串在S中出现的次数,这里循环串的定义是:对于一个长度为len的字符串,我们把它首尾相接,然后从任意位置开始走len步所得到的串我们叫做T的循环串。如abaa的循环串有 abaa,baaa,aaab,aaba。(注意如果重复只算一次。比如aaa的循环串只有一个aaa)

后缀自动机。。。

这题就是求几个串的出现次数罢了。。。

所以把S建成sam,然后把T * 2变成T',拿T'在sam上面跑。

维护一个匹配长度。如果超过T的长度就要减成T的长度,然后记得看一下当前这个串是否属于点p,也就是if l[fa[p]]>=len(T) then p = fa[p];

然后就没有然后了~

代码

再试一下github的高亮:

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project