BZOJ 1717 [Usaco2006 Dec]Milk Patterns 产奶的模式

发布于 2017-07-15  154 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1717

题意:求最长可重叠 k 次重复子串


论文题,简单说一下吧:

从经典问题引入:

求可重叠最长重复子串

这个显然就是 height 里的最大值,因为一个重复子串就是两个后缀的 lcp,还是显然的吧 T.T

求不可重叠最长重复子串

多了一个不可重叠的限制,不好判断是否合法。那么二分答案,转化为判定性问题:是否存在长度为 k 的不重叠重复子串。二分答案的正确性是显然的...

这里有一个很有趣的思想:对 height 分组,利用了 height 排好序的特点

在 height 小于 k 的地方分组,这样合法答案一定在同组中产生了。只需要判断同组 height 的 sa 最值差是否大于等于 k,有一组满足则均满足

求最长可重叠 k 次重复子串

终于到本题了,仿照上题的思想,依旧二分答案+height 分组。判断的方法是很简单的:是否存在大小大于等于 mid 的组即可

由于数字范围很大,离散化一发会比较优越,然而我懒

 

 


一个非常弱的准退役OIER