|
POJ3261:Milk Patterns 题意：给定一个字符串，求至少出现k次的最长重复子串，这k个子串可以重叠； 思路：这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。 不同的是，这里要判断的是有没有一个组的后缀个数不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。这个做法的时间复杂度为O(nlogn)。
/*
*
* 倍增算法（n*logn）
* 待排序数组长度为n，放在0~n-1中，在最后补0
* sa为后缀数组，把后缀从小到大排序把后缀开头存起来，rank为名次数组，以i开头的后缀在所有后缀中排第几
* sa的有效值为1~n，sa[0]必为n无效
* rank的有效值为0~n-1，rank[n]必为0无效
* height的有效值为2~n，前两个为0
*
*/
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e6+10;
int x[maxn];
int wa[maxn],wb[maxn],ww[maxn],wv[maxn],nn,k;
int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)//求的数组，得到的后缀数组，最长长度+1，数组里的最大值（一般180或者255）；
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i |