题解 [牛客练习赛61E] 相似的子串
相似的子串
https://ac.nowcoder.com/acm/contest/5026/E
题目描述
给定一个字符串,询问出现次数大于等于 的最长子串的长度(子串不相交)。
正解
二分 + 哈希。
首先答案显然满足单调性。
二分长度 后,如何判断答案可行?
设 表示以
为开头,长度为
的子串,到
为止,在不相交的情况下,最多出现了多少次。
更新 数组的时候有个比较显的然贪心,即记录从左往右扫的时候,最右出现的与
相同的子串(且与当前子串不相交)出现位置的开头。
查找子串的时候利用哈希表查询相同的哈希值即可。
如何做到不相交?
一个子串的 数组记录在开头,而在子串的尾巴位置插入哈希表,就可以做到不相交。
时间复杂度 。
一开始交了一发 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; }