后缀数组笔记。

由于子串等价于后缀的前缀，相当于在后缀排序之后一段连续后缀的公共前缀。
由公共前缀联想到 $\text{LCP}$，又因为至少出现 $k$ 次，因此只要在排序之后求所有长度为 $k-1$ 的区间的 $height$ 最大值即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5, M = 2e6 + 5;
int n, k, Mx, s[N];

int sa[N], rk[N], x[N], y[N];
int cnt[M];
void init_SA() {
    int v = Mx;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[x[i] = s[i]];
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;

    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[x[i]];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1];
        if (now) now--;
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

int q[N], st, ed, ans = 0;
void solve() {
    st = 1, ed = 0;
    for (int i = 1; i <= n; i++) {
        while (st <= ed && q[st] <= i - k + 1) st++;
        while (st <= ed && ht[q[ed]] > ht[i]) ed--;
        q[++ed] = i, ans = max(ans, ht[q[st]]);
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]), Mx = max(Mx, s[i]);
    init_SA(), init_height();
    solve();
    return 0;
}