题解 [牛客练习赛61E] 相似的子串

• 相似的子串

题目描述

给定一个字符串，询问出现次数大于等于 的最长子串的长度（子串不相交）。

正解

二分 + 哈希。

首先答案显然满足单调性。

二分长度 后，如何判断答案可行？

设 表示以 为开头，长度为 的子串，到 为止，在不相交的情况下，最多出现了多少次。

更新 数组的时候有个比较显的然贪心，即记录从左往右扫的时候，最右出现的与 相同的子串（且与当前子串不相交）出现位置的开头。

查找子串的时候利用哈希表查询相同的哈希值即可。

如何做到不相交？

一个子串的 数组记录在开头，而在子串的尾巴位置插入哈希表，就可以做到不相交。

时间复杂度 。

一开始交了一发 map 的，多了个 然后没过 QnQ。

#include <bits/stdc++.h>
#define N 200005

using namespace std;
typedef unsigned long long ULL;

const int base = 127;

unordered_map<ULL, int> las;

int n, k, ans;
char s[N];
ULL ha[N], pw[N];
int f[N];

inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}

ULL calc(int l, int r) {
    return ha[l] - pw[r - l + 1] * ha[r + 1];
}

int check(int x) {
    f[0] = 0;
    int res = 0;
    for (int i = 1; i <= n - x + 1; i++) {
        if (i - x > 0)
            las[calc(i - x, i - 1)] = i - x;
        f[i] = f[las[calc(i, i + x - 1)]] + 1;
        res = max(res, f[i]);
    }
    for (int i = 1; i <= n - x + 1; i++)
        las[calc(i, i + x - 1)] = 0;
    return res >= k;
}

int main() {
    n = read(), k = read();
    scanf("%s", s + 1);

       ha[n + 1] = 0;
    for (int i = n; i >= 1; i--)
        ha[i] = ha[i + 1] * base + s[i] - 'a';

    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * base;

    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = max(ans, mid);
            l = mid + 1;
       } else {
            r = mid - 1;
        }
    }

    printf("%d\n", ans);
    return 0;
}