题目描述
给你一个小写字母组成的字符串，求出一个这样一个最长子串，满足：
- 其在原串的不同位置出现了两次(起始位置不同，可以部分重叠)
- 其反串在原串中出现了一次(与前面两次无关)
数据范围
字符串长度 \(n \le 5e4\)
方法
考虑前缀哈希 + 二分。
如果说假设满足要求的子串为 \(s\) ，若存在 \(s\) 的长度等于 \(n\) ，那一定存在长度小于 \(s\) 的子串满足要求（比如 \(s\) 的子串），所以不难看出本题答案是具有单调性的。
现在我们可以二分答案，只需考虑 check() 的写法。
因为我们二分了满足条件的字串的长度（假设为\(l\)），我们考虑开个桶，统计每个字符串出现的个数。再在反串中验证每个长度为 \(l\) 的串在正串中出现的次数是否有大于等于 \(2\) 的。
具体的实现有很多种，可以开一个 map <string, int>， 或者前缀哈希加桶。我选择了最垃圾的方法是 map <int, int> 加上一个类似st表的哈希，用倍增将子串的哈希值拼起来。
时间复杂的： \(O (n log^k n)\) ,由于方法不同 \(k\) 可能在 1~3 中任意的数，但对于 \(5e4\) 的数据是绝对能过得。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define usd unsigned
#define el cout << '\n'
#define lowbit(x) (x & (-x))
const int ranmod = 1e7;
#define random ((rand() * rand()) % ranmod)
#define AC return
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
// void init();
void main_();
signed main() {ios :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);// freopen("similarity.in", "r", stdin);// freopen("similarity.out", "w", stdout);int t = 1;// cin >> t;while(t--) {// init();main_();}AK;
}
const int mod = 95225987, maxn = 5 * 1e5 + 18;
const usd int p = 2591;string s, s1;
int n;
usd int hsh[maxn][16], hsh1[maxn][16], nxt[maxn][16];
map <usd int, long> cnt;usd int ksm(usd int a, usd int b) {usd int res = 1;do {if(b & 1) res *= a;a *= a, b = b >> 1;} while(b);return res;
}bool check(int num) {// debug(num);cnt.clear();for(int i = 1; i <= n; i++) {if(i + num - 1 > n) break;usd int fl = i, hs = 0;for(int k = 15; k >= 0; k--) {if(fl + (1ll << k) <= i + num) {hs = hs * ksm(p, (1ll << k)) + hsh[fl][k];fl += (1ll << k);}}// debug(hs);cnt[hs]++;}for(int i = 1; i <= n; i++) {if(i + num - 1 > n) break;usd int fl = i, hs = 0;for(int k = 15; k >= 0; k--) {if(fl + (1ll << k) <= i + num) {hs = hs * ksm(p, (1ll << k)) + hsh1[fl][k];fl += (1ll << k);}}if(cnt[hs] >= 2) {// debug(num), debug(i);// debug(hs), debug(cnt[hs]);return true;}}return false;
}void main_() {cin >> s;n = s.length();for(int i = n - 1; i >= 0; i--) s1 += s[i];s = ' ' + s;s1 = ' ' + s1;for(int i = 1; i <= n; i++) hsh[i][0] = s[i], hsh1[i][0] = s1[i];for(int k = 1; k <= 15; k++) {for(int i = 1; i <= n; i++) {if(i + (1ll << (k - 1)) - 1 > n) continue;hsh[i][k] = hsh[i][k - 1] * ksm(p, 1ll << (k - 1)) + hsh[i + (1ll << (k - 1))][k - 1];hsh1[i][k] = hsh1[i][k - 1] * ksm(p, 1ll << (k - 1)) + hsh1[i + (1ll << (k - 1))][k - 1];}}int l = 2, r = n, ans = 1;while(l <= r) {int mid = l + (r - l) / 2;if(check(mid)) {ans = mid;l = mid + 1;}else r = mid - 1;}cout << ans; el;
}