[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)

发布于 2018-03-24  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的,如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的,因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。

Tag

后缀数组,ST表

解决思路

如果枚举长度l,再枚举一个位置pos,那么问题就变成询问两个后缀的lcp。这个可以在求出后缀数组后,求两个后缀对应之间的Height的最小值,而区间最小值可以用ST表求。
但如果枚举所有位置是不行的。考虑到循环重复串的性质,我们可以只枚举是l的倍数的地方的串查询lcp。
但这样若答案的开始的位置不在l的倍数的位置,就会有问题。但我们发现,在l的倍数的位置求出lcp能够帮助我们找到这个循环串的开头的位置,即当前位置-l+r%l,r为我们找到的lcp长度。那么在这个位置再求一次lcp即可。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[hihocoder1419]后缀数组四·重复旋律4(后缀数组,ST表)


HNCJ OIer 一枚