poj 3261 Milk Patterns (最长公共子串,后缀数组)

poj3261

题意:给一个字符串,要求找出至少出现k次的最长重复子串…

思路:后缀数组,然后再次用到了根据height数组对后缀进行分组的套路…二分判定合法性,对于当前的最长长度x,分组使得每组中的height[i]都大于等于x,所不同的是,判定变成了存在一个组,后缀的个数至少为k个(因为这样,就可以对于大于等于k个的后缀,同时取前x长度,得到的就是出现了至少k次且长度为x的前缀)1A,蛤蛤蛤

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz