题目链接 \(Click\) \(Here\)

水题。利用\(Height\)的性质维护一个单调栈即可。

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1000010;

int n, m = 1000000, q, s[N], sa[N], tp[N];

int rk[N], _rk[N], bin[N], height[N];

void base_sort () {

    for (int i = 0; i <= m; ++i) bin[i] = 0;

    for (int i = 1; i <= n; ++i) bin[rk[tp[i]]]++;

    for (int i = 1; i <= m; ++i) bin[i] += bin[i - 1];

    for (int i = n; i >= 1; --i) sa[bin[rk[tp[i]]]--] = tp[i];

}

void suffix_sort () {

    for (int i = 1; i <= n; ++i) {

        tp[i] = i;

        rk[i] = s[i];

    }

    base_sort ();

    for (int w = 1; w <= n; w <<= 1) {

        int cnt = 0;

        for (int i = n - w + 1; i <= n; ++i) {

            tp[++cnt] = i;

        }

        for (int i = 1; i <= n; ++i) {

            if (sa[i] > w) {

                tp[++cnt] = sa[i] - w;

            }

        }

        base_sort ();

        memcpy (_rk, rk, sizeof (rk));

        rk[sa[1]] = cnt = 1;

        for (int i = 2; i <= n; ++i) {

            rk[sa[i]] = _rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w] ? cnt : ++cnt;

        }

        if (cnt == n) break;

        m = cnt;

    }

    // printf ("sa : ");for (int i = 1; i <= n; ++i) printf ("%d ", sa[i]); printf ("\n");

}

void get_height () {

    int k = 0;

    for (int i = 1; i <= n; ++i) {

        if (k) k--;

        int j = sa[rk[i] - 1];

        while (s[i + k] == s[j + k]) ++k;

        height[rk[i]] = k;

    }

    // printf ("height : ");

    // for (int i = 1; i <= n; ++i) {

    // 	printf ("%d ", height[i]);

    // }

    // printf ("\n");

}

int que[N];

int main () {

	cin >> n >> q;

	for (int i = 1; i <= n; ++i) {

	    cin >> s[i];

	}

    suffix_sort ();

    get_height ();

	int head = 1, tail = 0, ans = -0x3f3f3f3f;

	for (int i = 1; i <= n; ++i) {

		while (head <= tail && height[que[tail]] >= height[i]) --tail;

		que[++tail] = i;

		while (head <= tail && i - que[head] >= q - 1) ++head;

		ans = max (ans, height[que[head]]);

	}

	cout << ans << endl;

}