POJ 3261 后缀数组 分组思想

题意:

给出一个串,求这个串的最长的出现过至少k次的子串。出现的位置可以重叠。

分析:

用后缀数组先处理出height数组,然后二分答案,根据limit将height分组,使得每一组里任意串的lcp>=limit。

然后如果某一组的串的个数超过>=k,那么flag=true。

插曲:

基数排序时e没有设为0,WA了和RE了好多遍。

code:

#include

加入对话

3条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注