【后缀数组】【LuoguP2852】 [USACO06DEC]牛奶模式Milk Patterns

题目链接

题目描述

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

思路：

实际上就是求可重叠的 \(k\) 次最长子串

这里给出单调队列的代码

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#define maxn 20010

using namespace std;

int n, K;

int a[maxn], cnt, b[maxn];

void init_hash() {

    for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); b[i] = a[i]; }

    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;

    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;

}

int tax[maxn], rk[maxn], tp[maxn], sa[maxn], M;

void rsort() {

    for (int i = 0; i <= M; ++i) tax[i] = 0;

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

    for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];

    for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];

}

int H[maxn];

void SA() {

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

    int c1 = 0; M = cnt; rsort();

    for (int k = 1; k <= n; k *= 2) {

        if (c1 == n) break; M = c1; c1 = 0;

        for (int i = n - k + 1; i <= n; ++i) tp[++c1] = i;

        for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++c1] = sa[i] - k;

        rsort(); swap(tp, rk); rk[sa[1]] = c1 = 1;

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

            if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++c1;

            rk[sa[i]] = c1;

        }

    }

    int lcp = 0;

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

        if (lcp) --lcp;

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

        while (a[j + lcp] == a[i + lcp]) ++lcp;

        H[rk[i]] = lcp;

    }

}

int Q[maxn], h = 1, t;

int ans;

int main() {

    scanf("%d%d", &n, &K); init_hash(); SA(); --K;

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

        while (h <= t && i - Q[h] >= K) ++h;

        while (h <= t && H[i] <= H[Q[t]]) --t;

        Q[++t] = i;

        if (i >= K) ans = max(ans, H[Q[h]]);

    } cout << ans << endl;

    return 0;

}