题解：P10915 [蓝桥杯 2024 国 B] 最长回文前后缀
tiko_tao
·
·
题解
update：修改了字符串使用行内代码块的问题。
P10915 [蓝桥杯 2024 国 B] 最长回文前后缀
题墓链接
都是从这里翻来的为什么要链接呢。
题意简述：给你一个字符串，你可以删掉其中连续的一段，使得操作后的字符串的前缀和后缀合并起来是一个回文串。
注意，这里的前缀和后缀不能交叉。
什么意思呢，就比如：
abccba是一个回文串，此时前缀abc 和后缀cba构成回文，因此这个长度为 3，答案为 0（不用删）。
而abcba虽然是一个回文串，但这时的最大长度只有 2，前缀为ab，后缀为ba，中间的 c 如果取的话，两个会交叉。
做法：字符串哈希加二分。
我们设 n 为字符串 s 的长度，题中说 |S|\le500000，即 n\le500000
看到这个复杂度，我们考虑 O(n) 做法或 O(n\log{n}) 做法。
首先，我们可以发现如果字符串原本的前缀和后缀可以构成回文，那么我们可以保留这些部分，将删字符的范围缩小，可以证明这样是最优的，已经有了为什么要删呢。
例：
abkxcvjha
乱编的这个字符串中原来头尾的 a 本就可以构成长度为 1 的回文，于是我们把字符串缩小，变成。
bkxcvj
在这个字符串中考虑删即可（虽然好像怎么删都没法改变答案）。
OK，这样我们就做完了第一步，这步的复杂度是 O(n)
的，对于整道题来说可以忽略不计。
经过第一步的删除，可以肯定现在字符串的两端一定是不同的，我们要删连续的一段，使前缀和后缀构成回文，因此我们一定是删去这个串的一个前缀或后缀。
考虑暴力。
假设我们先枚举删前缀的情况。
用一个循环枚举我们删掉前缀的字母个数，这个时候我们只要每次把前 i 个字符忽略，再判断后面字符串可构成回文的前后缀最长长度，最后取个 \max 即可。
传统判断前后缀方法，用双指针对前后缀进行匹配，复杂度 O(n)。
啊如果采用这种方法的话我们的程序就达到了赤石优秀的 O(n^2)。
那这个地方有两个地方可以优化。
1：枚举删掉的前缀长度 O(n) 优化？
2：判断回文优化。
1 好像是比较难搞得，但 2 看起来肥肠有前途。
因为有个叫字符串哈希的东西，可以 O(1) 来判断两段字符串是否相等。
如果不会可以去做一下模版题 这
我就不详细讲了因为我也刚会。
我们现在还剩 O(\log{n}) 的复杂度，在哈希的基础上，我们要想想怎么在 \log 的时间内找到我们要找的最大长度，即构成回文的前缀后缀在字符串中的断点。
很自然可以想到二分。
二分怎么做呢， 举个例子，假设我们现在有这样一个字符串。
```
abcdefafeba
```
用第一步删去头尾。
```
cdefafe
```
我我们要删的是前缀（先假设删前缀）。
$i = 1$ 时，头尾不相等，无法构成。
$i = 2$ 时，字符串变成这样。
```
efafe
```
我们发现如果我们枚举到的前缀和后缀是满足条件的，那么这个**前缀的前缀**和**长度相同的后缀的后缀**那一定也是可以构成回文的。
如此，则满足单调性，可以进行二分。
考虑二分**满足条件串的长度**。
由于不能交叉，因此 $l$ 初始值为 1, $r$ 初始值为当前子串长 $n / 2$。
至于哈希，维护两个哈希数组，分别记录前缀和后缀哈希值即可。
至此，我们得到了 $O(n\log{n})$ 的方法。
因为现在考虑的是只去前缀，事实上后缀是同理的，所以我偷懒写了个函数，然后把 $s$ 翻转了一下再做一遍前缀，这样当然也是可以的 qwq。
部分注释写在代码里了 qwq。
```cpp
#include <bits/stdc++.h>
#define rep(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define pre(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)
#define ull unsigned long long
#define int long long
using namespace std;
const int N = 1000000 + 10;
const ull Hash = 911; //为了防止被卡，而且发现911也是一个质数qwq
ull ha[N], hb[N], pw[N]; //哈希自然溢出
ull gethash(ull t[], int l, int r)
{
return t[r] - t[l - 1] * pw[r - l + 1]; //取区间字符串哈希值11
}
int solve(string s)
{
int n = s.size();
s = " " + s; //在s前插一个空格，这样下标就从1开始了
pw[0] = 1;
rep(i, 1, n)
{
pw[i] = pw[i - 1] * Hash; //预处理次方数组，因为是自然溢出不用取模
ha[i] = ha[i - 1] * Hash + s[i]; //维护前缀哈希值
hb[i] = hb[i - 1] * Hash + s[n - i + 1]; //维护后缀哈希值
}
int mx = 0; //记录最大答案
rep(i, 1, n)
{
int l = 1, r = (n - i) / 2; //r从现有长度 / 2开始
while (l <= r)
{
int mid = l + r >> 1;
if (gethash(ha, 1, mid) == gethash(hb, i + 1, i + mid))
//判断长度为mid前后缀哈希值是否相等，其中后缀哈希数组对应的下标需要推一下
l = mid + 1;
else r = mid - 1;
}
mx = max(mx, r);
}
return mx;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s;
cin >> s;
int n = s.size();
int l = 0, r = n - 1; //第一步
while (s[l] == s[r] && l <= r) l++, r--;
if (l > r) cout << l; //如果l>r说明本来就是一个回文串，不用删，l即为答案
else
{
s = s.substr(l, r - l + 1); //取出删掉前后缀的字符串
string t = s; //用另一个字符串做后缀
reverse(t.begin(), t.end()); //翻转
cout << max(solve(s), solve(t)) + l;
}
return 0;
}
```