还是2009那篇论文里介绍的做法
有下载链接
#include#include #include using namespace std;int k, n, rnk[20005], sa[20005], s[20005], H[20005], c[20005], K;void Sort(int *x, int *y, int *rk) { static int C[20005]; for (int i = 0; i <= k; ++i) C[i] = 0; for (int i = 1; i <= n; ++i) ++C[rk[i]]; for (int i = 1; i <= k; ++i) C[i] += C[i - 1]; for (int i = n; i; --i) y[C[rk[x[i]]]--] = x[i];}inline bool cmp(int *y, int a, int b, int m) {return y[a] == y[b] && y[a + m] == y[b + m];}void get_SA() { static int Y[20005]; int *y = Y, *rk = rnk; for (int i = 1; i <= n; ++i) y[i] = s[i]; sort(y + 1, y + 1 + n); int m = unique(y + 1, y + 1 + n) - y - 1; for (int i = 1; i <= n; ++i) s[i] = lower_bound(y + 1, y + 1 + m, s[i]) - y; for (int i = 1; i <= n; ++i) rk[i] = s[y[i] = i]; k = 20003; Sort(y, sa, rk); for (int m = 1, p = 0; p < n; k = p, m <<= 1) { for (p = 0; p < m; ++p) y[p + 1] = n - m + p + 1; for (int i = 1; i <= n; ++i) if (sa[i] > m) y[++p] = sa[i] - m; Sort(y, sa, rk), swap(y, rk); rk[sa[p = 1]] = 1; for (int i = 2; i <= n; ++i) rk[sa[i]] = cmp(y, sa[i - 1], sa[i], m) ? p : ++p; } for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;}void get_H() { for (int i = 1, k = 0; i <= n; H[rnk[i++]] = k) for (k ? --k : 0; s[i + k] == s[sa[rnk[i] - 1] + k]; ++k);}bool check(int x) { for (int i = 2, cnt = 1; i <= n; ++i) { if (H[i] >= x) ++cnt; else cnt = 1; if (cnt == K) return 1; } return 0;}int main() { while (~scanf("%d%d", &n, &K) && n) { for (int i = 1; i <= n; ++i) scanf("%d", s + i), ++s[i]; get_SA(); get_H(); int l = 1, r = n, mid; while (l <= r) { if (check(mid = l + r >> 1)) l = mid + 1; else r = mid - 1; } cout << l - 1 << endl; } return 0;}