DDOSvoid's Blog

Luogu P2852 [USACO06DEC]Milk Patterns G

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P2852

简要题意：给定一个长度为 $n$ 的字符串和 $k$，求长度最长的一个子串，满足这个子串至少出现了 $k$ 次

$n\le 2\times 10^4$

Solution

我们仍然考虑二分答案 $x$

我们考虑如果有一个满足条件的子串出现了 $k$ 次，那么我们把这 $k$ 个起始位置拿出来，这些位置的 $lcp$ 显然要大于等于 $x$

那么我们相当于二分只有需要判断是否存在一个长度为 $k-1$ 的区间满足区间最小值大于等于 $x$

显然可以单调队列维护，然后我们甚至可以将二分去掉，时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <queue>
#define maxn 20010
#define ll long long
using namespace std;

int n, k;
int s[maxn];

int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255;
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 init_sa() {
    if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1; 
    for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
    for (int k = 1; k < n; k *= 2) {
        if (cnt == n) break; M = cnt; cnt = 0;
        for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
        rsort(); swap(rk, tp); rk[sa[1]] = cnt = 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]) ++cnt;
            rk[sa[i]] = cnt;
        }
    } int lcp = 0;
    for (int i = 1; i <= n; ++i) {
        if (lcp) --lcp;
        int j = sa[rk[i] - 1];
        while (s[j + lcp] == s[i + lcp]) ++lcp;
        H[rk[i]] = lcp;
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> s[i];
    init_sa(); deque<int> Q; int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && H[i] < H[Q.back()]) Q.pop_back();
        Q.push_back(i); 
        while (!Q.empty() && i - Q.front() + 1 >= k) Q.pop_front();
        ans = max(ans, H[Q.front()]); 
    } cout << ans << "\n"; 
    return 0;
}