https://ac.nowcoder.com/acm/contest/5026

E. 相似的子串

 

题意：给定字符串和k，要找出k个不相交的子串，最长公共前缀大于等于x，求最大的x。

二分+字符串哈希

二分结果长度，因为显然答案单调，即越短，越会成功。

固定长度check是否有至少k个不相交子串最长公共前缀大于等于x，等价变为k个等于x的不相交子串，las[i]las[i] 记录哈希值为i的字符串在左边最近出现的位置。 dp[i]dp[i] 记录以第i位开头，长为check的长度的串出现次数。

每次在串结尾更新las保证不会相交。

关于二分，看 https://www.woria.xyz/2020/01/19/ecr80/#D-Minimax-Problem

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int base = 127;
int n, k, dp[N];
char s[N];
ull ha[N], pw[N];
unordered_map<ull, int>las;
ull cal(int l, int r) {
    return ha[r] - ha[l - 1] * pw[r - l + 1];
}
bool check(int len) {
    las.clear();
    int res = 0;
    for (int i = 1; i <= n - len + 1; i++) {
        ull hah = cal(i, i + len - 1);
        if (i - len >= 1)las[cal(i - len, i - 1)] = i - len;
        if (las.count(hah))dp[i] = dp[las[hah]] + 1;
        else dp[i] = 1;
        res = max(res, dp[i]);
    }
    return res >= k;
}
int main() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    pw[0] = 1ll;
    for (int i = 1; i <= n; i++) {
        ha[i] = ha[i - 1] * base + s[i] - 'a';
        pw[i] = pw[i - 1] * base;
    }
    int L = 0, R = n;
    while (L < R) {
        int mid = (L + R + 1) / 2;
        if (check(mid))L = mid;
        else R = mid - 1;
    }
    printf("%d\n", L);
    return 0;
}