[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)

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


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

本文链接地址:[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)

Description

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。

旋律可以表示为一段连续的数列,相似的旋律在原数列不可重叠,比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次,2 3 出现了两次,小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少?

Tag

后缀数组,二分

解决思路

这一题的基础上,要求不能出现重叠。考虑到这个答案具有单调性,那么我们二分这个长度是多少,二分判定的时候,判断在连续的一段Height大于等于当前二分长度的后缀中,是否存在两者距离超过当前二分长度的。
需要注意在不连续的时候要更新当前的min和max。

代码

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

本文链接地址:[hihocoder1407]后缀数组二·重复旋律2(后缀数组,二分)


HNCJ OIer