自动搬运

查看原文

来自洛谷，原作者为

	tiko_tao 我是shaber

搬运于2025-08-24 23:02:29，当前版本为作者最后更新于2024-10-18 20:52:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$ 的时间内找到我们要找的最大长度，即构成回文的前缀后缀在字符串中的断点。

$\log$ 的算法？
很自然可以想到二分。
二分怎么做呢， 举个例子，假设我们现在有这样一个字符串。

abcdefafeba

用第一步删去头尾。

cdefafe

我我们要删的是前缀（先假设删前缀）。
$i = 1$ 时，头尾不相等，无法构成。
$i = 2$ 时，字符串变成这样。

efafe

我们发现如果我们枚举到的前缀和后缀是满足条件的，那么这个前缀的前缀和长度相同的后缀的后缀那一定也是可以构成回文的。

如此，则满足单调性，可以进行二分。
考虑二分满足条件串的长度。
由于不能交叉，因此 $l$ 初始值为 1, $r$ 初始值为当前子串长 $n / 2$。
至于哈希，维护两个哈希数组，分别记录前缀和后缀哈希值即可。

至此，我们得到了 $O(n\log{n})$ 的方法。
因为现在考虑的是只去前缀，事实上后缀是同理的，所以我偷懒写了个函数，然后把 $s$ 翻转了一下再做一遍前缀，这样当然也是可以的 qwq。

部分注释写在代码里了 qwq。

#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;
}