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
     
       #include
      
        #include
       
         #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; }