[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)

发布于 2018-03-20  182 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。

小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列,相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。

小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少?

Tag

后缀数组

解决思路

提出所有的后缀后,相同旋律就是后缀中相同的前缀,那么出现次数为K就是要求重复了K次的相同前缀。
后缀数组求出Height后,问题转化为求连续的K个值的最小值中的最大值,这个可以用单调队列来维护。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[hihocoder1403]后缀数组一·重复旋律(后缀数组,单调队列)


HNCJ OIer