一个小问题
Statement
来源:https://www.luogu.com.cn/problem/T297472?contestId=91205
给定字符串 \(S\),求最长的连续子序列满足其中每个字符都出现了偶数次,求最长长度。
\(T\) 组询问,\(\displaystyle \sum_{}|S| \leq 5\times 10^6\)。
注:本题暂时只需要通过 \(\text{Subtask 4}\) 即可,原题的 hack 数据在时间限制和空间限制上都不太够。
Solution
前置知识:哈希。
这个题要求每个字符都出现偶数次,这种感觉就是异或的值为 \(\textbf{0}\)。
就引入异或哈希这个玩意。
其方法就是,在 \([0,L]\) 的范围内给每个字符都随机生成一个,代码如下:
const ll mod = 1048576;
mt19937_64 maker (time (NULL));
inline void gen () {
for (ll _ = 0;_ < need; ++ _) {
for (ll i = 0;i <= 256; ++ i) a[_][i] = maker () % mod;
}
}
注意 \(L\) 一定要是形如 \(2^N\) 的数,比如 \(2^{20}=1048576\)。
剩下的我们就记录每一个哈希结果最早出现的下标,第二次出现的时候就计入答案即可。
inline ll solve (ll can) {
fir[0] = 0;
lpos[0] = can;
ll XOR = 0, Result = -1;
for (ll i = 1;i <= n; ++ i) {
XOR ^= a[can % need][(ll) s[i]];
if (lpos[XOR] == can) {
Result = max (Result, i - fir[XOR]);
}
else {
fir[XOR] = i;
lpos[XOR] = can;
}
}
return Result;
}
为了保险,我们要做 \(10\) 次 solve()
函数。