POJ_3261
这个题目和POJ_1743差不多，但需要求的是重复至少K次的子串。
我们可以通过二分子串的长度k来做，这时就将题目变成了是否存在重复次数至少为K次且长度不小k的字符串。首先我们可以把相邻的所有不小于k的height[]看成一组，这组内有多少个字符串，就相当于有多少个长度至少为k的重复的子串。
之所以可以这么做，是因为排名第i的字符串和排名第j的字符串的最长公共前缀等于height[i],height[i+1],...,height[j]中的最小值，所以把所有不小于k的height[]看成一组就保证了组内任意两个字符串的最长公共前缀都至少为k，且长度为k的前缀是每个字符串共有的，因此这组内有多少个字符串，就相当于有多少个长度至少为k的重复的子串（任意一个子串都是某个后缀的前缀）。
我的代码写得相对繁琐一些了，因为“奶”的取值最大能到1000000，这样一开始如果做基数排序的话确实花费的时间比较高，而N只有20000，所以前面两次排序如果用快排的话会快一些。如果都用基数排序也没有关系，因为两次基数排序过后，m的值就会约为N或比N小。
当然，如果这个题目“奶”的取值最大到10^8或类似的比较大的范围，那么前两次排序就只能用快排了。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 20010
int N, K, r[MAXD], sa[MAXD], rank[MAXD], height[MAXD], wa[MAXD], wb[MAXD], ws[MAXD], wv[MAXD];
void init()
{
int i, j, k;
for(i = 0; i < N; i ++)
{
scanf("%d", &r[i]);
++ r[i];
}
r[N] = 0;
}
int cmp1(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
if(r[*p] == r[*q])
return *p - *q;
else
return r[*p] - r[*q];
}
int cmp2(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
if(wv[*p] == wv[*q])
return *p - *q;
else
return wv[*p] - wv[*q];
}
int cmp(int *p ,int x, int y, int l)
{
return p[x] == p[y] && p[x + l] == p[y + l];
}
void da(int n, int m)
{
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < n; i ++)
ws[i] = i, x[i] = r[i];
qsort(ws, n, sizeof(ws[0]), cmp1);
for(i = 0; i < n; i ++)
sa[i] = ws[i];
for(p = 1, j = 1; p < n; j *= 2, m = p)
{
for(p = 0, i = n - j; i < n; i ++)
y[p ++] = i;
for(i = 0; i < n; i ++)
if(sa[i] >= j)
y[p ++] = sa[i] - j;
for(i = 0; i < n; i ++)
wv[i] = x[y[i]];
if(m > 1000000)
{
for(i = 0; i < n; i ++)
ws[i] = i;
qsort(ws, n, sizeof(ws[0]), cmp2);
for(i = 0; i < n; i ++)
sa[i] = y[ws[i]];
}
else
{
for(i = 0; i < m; i ++)
ws[i] = 0;
for(i = 0; i < n; i ++)
++ ws[wv[i]];
for(i = 0; i < m; i ++)
ws[i] += ws[i - 1];
for(i = n - 1; i >= 0; i --)
sa[-- ws[wv[i]]] = y[i];
}
for(t = x, x = y, y = t, x[sa[0]] = 0, p = 1, i = 0; i < n; i ++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1: p ++;
}
}
void calheight(int n)
{
int i, j, k = 0;
for(i = 1; i <= n; i ++)
rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k)
for(k ? -- k : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k ++);
}
void solve()
{
int i, j, k, cnt, ans, mid, min, max;
da(N + 1, 1000002);
calheight(N);
min = 1, max = N;
for(;;)
{
mid = (max + min) / 2;
if(mid == min)
break;
ans = cnt = 0;
for(i = 1; i <= N; i ++)
{
if(height[i] < mid)
{
if(cnt > ans)
ans = cnt;
cnt = 0;
}
else
{
if(!cnt)
cnt = 2;
else
++ cnt;
}
}
if(cnt > ans)
ans = cnt;
if(ans >= K)
min = mid;
else
max = mid;
}
printf("%d\n", mid);
}
int main()
{
while(scanf("%d%d", &N, &K) == 2)
{
init();
solve();
}
return 0;
}