这也是一道例题
给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。
算法分析：
这题的做法和上一题差不多，也是先二分答案，然后将后缀分成若干组。不
同的是，这里要判断的是有没有一个组的后缀个数不小于 k。如果有，那么存在
k 个相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn)。
我们可以通过二分子串的长度k来做，这时就将题目变成了是否存在重复次数至少为K次且长度不小k的字符串。
首先我们可以把相邻的所有不小于k的height[]看成一组，这组内有多少个字符串，
就相当于有多少个长度至少为k的重复的子串。
之所以可以这么做，是因为排名第i的字符串和排名第j的字符串的最长公共前缀
等于height[i],height[i+1],...,height[j]中的最小值，所以把所有不小于k的height[]看成
一组就保证了组内任意两个字符串的最长公共前缀都至少为k，且长度为k的前缀是每个字符串共有的，
因此这组内有多少个字符串，就相当于有多少个长度至少为k的重复的子串（任意一个子串都是某个后缀的前缀）。
Source Code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = ;
const ll P = 10000000097ll ;
const int INF = 0x3f3f3f3f ; int a[M], sa[M], h[M], rank[M]; void radix(int *str, int *a, int *b, int n, int m){
static int count[M];
int i;
memset(count, , sizeof(count));
for(i = ; i < n; ++i) ++count[str[a[i]]];
for(i = ; i <= m; ++i) count[i] += count[i - ];
for(i = n - ; i >= ; --i) b[--count[str[a[i]]]] = a[i];
} void suffix_array(int *str, int *sa, int n, int m){
static int a[M], b[M];
int i, j;
for(i = ; i < n; ++i) rank[i] = i;
radix(str, rank, sa, n, m); rank[sa[]] = ;
for(i = ; i < n; ++i) rank[sa[i]] = rank[sa[i - ]] + (str[sa[i]] != str[sa[i - ]]);
for(i = ; <<i < n; ++i){
for(j = ; j < n; ++j){
a[j] = rank[j] + ;
b[j] = j + ( << i) >= n ? : rank[j + ( << i)] + ;
sa[j] = j;
}
radix(b, sa, rank, n, n);
radix(a, rank, sa, n, n);
rank[sa[]] = ;
for(j = ; j < n; ++j){
rank[sa[j]] = rank[sa[j - ]] + (a[sa[j - ]] != a[sa[j]] || b[sa[j - ]] != b[sa[j]]);
}
}
} void calc_height(int *str, int *sa, int *h, int n){
int i, k = ;
h[] = ;
for(i = ; i < n; ++i){
k = k == ? : k - ;
if(rank[i] != ){
while(str[i + k] == str[sa[rank[i] - ] + k]){
++k;
}
}
h[rank[i]] = k;
}
} void solve_duplicate_substr(int n){
int i, j, pos, ans = ;
for(i = ; i < n; ++i){
if(h[rank[i]] > ans){
ans = h[rank[i]];
pos = i;
}
}
for(i = pos; i < pos + ans; ++i){
printf("%c", a[i]);
}
printf("\n");
} void slove_update_duplicate_substr(int n, int k){
int i, j;
int low = , high = n;
int ans = , pos1 = , pos2 = ;
while(low <= high){
int mid = (low + high) / ;
bool flag = false;
for(i = ; i < n; ++i){
if(h[i] >= mid){
++ans;
if(ans >= k) flag = true;
}
else ans = ;
}
if(flag) low = mid + ;
else high = mid - ;
}
cout << high << endl;
} int main(){
int i, j, t, n, m, k;
while(cin >> n >> k){
for(i = ; i < n; ++i) cin >> a[i];
suffix_array(a, sa, n, );
calc_height(a, sa, h, n);
slove_update_duplicate_substr(n, k);
}
return ;
}