这也是一道例题
给定一个字符串，求至少出现 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-7 ; const int N = 1 ; const int M = 200000 ; 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, 0, sizeof(count)); for(i = 0; i < n; ++i) ++count[str[a[i]]]; for(i = 1; i <= m; ++i) count[i] += count[i - 1]; for(i = n - 1; i >= 0; --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 = 0; i < n; ++i) rank[i] = i; radix(str, rank, sa, n, m); rank[sa[0]] = 0; for(i = 1; i < n; ++i) rank[sa[i]] = rank[sa[i - 1]] + (str[sa[i]] != str[sa[i - 1]]); for(i = 0; 1<<i < n; ++i){ for(j = 0; j < n; ++j){ a[j] = rank[j] + 1; b[j] = j + (1 << i) >= n ? 0 : rank[j + (1 << i)] + 1; sa[j] = j; } radix(b, sa, rank, n, n); radix(a, rank, sa, n, n); rank[sa[0]] = 0; for(j = 1; j < n; ++j){ rank[sa[j]] = rank[sa[j - 1]] + (a[sa[j - 1]] != a[sa[j]] || b[sa[j - 1]] != b[sa[j]]); } } } void calc_height(int *str, int *sa, int *h, int n){ int i, k = 0; h[0] = 0; for(i = 0; i < n; ++i){ k = k == 0 ? 0 : k - 1; if(rank[i] != 0){ while(str[i + k] == str[sa[rank[i] - 1] + k]){ ++k; } } h[rank[i]] = k; } } void solve_duplicate_substr(int n){ int i, j, pos, ans = 0; for(i = 0; 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(" "); } void slove_update_duplicate_substr(int n, int k){ int i, j; int low = 1, high = n; int ans = 0, pos1 = 0, pos2 = 0; while(low <= high){ int mid = (low + high) / 2; bool flag = false; for(i = 0; i < n; ++i){ if(h[i] >= mid){ ++ans; if(ans >= k) flag = true; } else ans = 1; } if(flag) low = mid + 1; else high = mid - 1; } cout << high << endl; } int main(){ int i, j, t, n, m, k; while(cin >> n >> k){ for(i = 0; i < n; ++i) cin >> a[i]; suffix_array(a, sa, n, 256); calc_height(a, sa, h, n); slove_update_duplicate_substr(n, k); } return 0; }