题意: 找出现至少k次的子串的最大长度.
思路：据贪心策略,子串变长答案不会减小,所以可以看做是求k个后缀的LCP.因为要求LCP的最大值,而LCP(suffix(sa[i]),suffix(sa[j]))=min{height[k]}(i<j,k∈[i,j]),显然当这k个后缀在排名上连续的时候可以取得最小值.因为若排名不连续,那么涵盖的取最小值的范围一定会变大,而当取值范围变大最小值只会变小.所以这个贪心是正确的.
二分 + 后缀数组（height数组）

我们知道，后缀(j)和后缀(k)的 最 长 公 共 前 缀 为height[rank[j]+1],

height[rank[j]+2],height[rank[j]+3],…,height[rank[k]]中的最小值(设rank[j]<rank[k])。

那么设k个后缀中rank的min=l，max=r，k个的最长公共前缀就是min(height[l+1->r])

所以k个后缀在rank上一定是连续的。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, k, p;
int s[maxn];
int sa[maxn], rak[maxn], tx[maxn], height[maxn], q[maxn];
struct node {
	int x, y, id;
}a[maxn],b[maxn];


void rsort() {
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[a[i].y]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		b[tx[a[i].y]--] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[b[i].x]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = n; i >= 1; i--) {
		a[tx[b[i].x]--] = b[i];
	}
}


void solve() {
	rsort();
	p = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) {
			++p;
		}
		rak[a[i].id] = p;
	}
	for (int i = 1; i <= n; i++) {
		a[i].x = rak[i];
		a[i].id = sa[rak[i]] = i;
		a[i].y = 0;
	}
	m = p;
}


void ssort() {
	for (int i = 1; i <= n; i++) {
		a[i].x = a[i].y = s[i];
		a[i].id = i;
		m = max(m, s[i]);
	}
	solve();
	for (int j = 1; j <= n; j <<= 1) {
		for (int i = 1; i + j <= n; i++) {
			a[i].y = a[i + j].x;
		}
		solve();
		if (p == n) {
			break;
		}
	}
}


void get_Height() {
	int k = 0;
	for (int i = 1; i <= n; i++) {
		if (k) {
			k--;
		}
		int j = sa[rak[i] - 1];
		while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) {
			k++;
		}
		height[rak[i]] = k;
	}
}

/* 5 2 1 2 1 2 1 */


int check(int x) {
	int i = 1;
	while (1) {
		for (; i <= n && height[i] < x; i++);
		if (i > n) {
			break;
		}
		int cnt = 1;
		for (; i <= n && height[i] >= x; cnt++, i++);
		if (cnt >= k) {
			return 1;
		}
	}
	return 0;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
	}
	ssort(); get_Height();
	int l = 1, r = n;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	printf("%d\n", l - 1);
	return 0;
}