Description

给定一个长度为 \(n\) 的字符串，求至少出现 \(k\) 次的最长重复子串，这 \(k\) 个子串可以重叠。

\(1\leq n\leq 20000\)

Solution

预处理好 \(height\) 之后，比较显然的是答案就是一段连续 \(k\) 个后缀内最小 \(height\) 值最大值。用滑动窗口维护就好了。

Code

#include 
    
     using namespace std;const int N = 20000+5, M = 1000000+5;int n, m, k, ch[N], x[N<<1], y[N<<1], c[M], sa[N], rk[N], height[N];int q[N], head, tail, ans;void get() {    for (int i = 1; i <= n; i++) c[x[i] = ch[i]]++;    for (int i = 1; i <= m; i++) c[i] += c[i-1];    for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;    for (int k = 1; k <= n; k <<= 1) {        int num = 0;        for (int i = n-k+1; i <= n; i++) y[++num] = i;        for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i]-k;        for (int i = 0; i <= m; i++) c[i] = 0;        for (int i = 1; i <= n; i++) c[x[i]]++;        for (int i = 1; i <= m; i++) c[i] += c[i-1];        for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];        swap(x, y); x[sa[1]] = num = 1;        for (int i = 2; i <= n; i++)            x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? num : ++num;        if ((m = num) == n) break;    }    for (int i = 1; i <= n; i++) rk[sa[i]] = i;    for (int i = 1, k = 0; i <= n; i++) {        if (rk[i] == 1) continue;        if (k) --k; int j = sa[rk[i]-1];        while (i+k <= n && j+k <= n && ch[i+k] == ch[j+k]) ++k;        height[rk[i]] = k;    }}void work() {    scanf("%d%d", &n, &k); m = M-5; --k;    for (int i = 1; i <= n; i++) scanf("%d", &ch[i]);    get(); tail = -1;    for (int i = 1; i <= n; i++) {        while (head <= tail && i-q[head] >= k) ++head;        while (head <= tail && height[i] <= height[q[tail]]) --tail;        q[++tail] = i;        if (i >= k) ans = max(ans, height[q[head]]);    }    printf("%d\n", ans);}int main() {work(); return 0; }