题解：P12213 [蓝桥杯 2023 国 Python B] 最长回文前后缀

P12213 最长回文子串 题解

本解法有些复杂，同时需要哈希和 manacher ，欢迎来化简。

题意

输入字符串 \(S\) ，取其中一个前缀和后缀，拼接后为回文串。
_{某蒟蒻（我）原来还以为可以把后缀放在前面}

思路

为了方便，以下令 \(n=|S|\) ，即字符串长度。

1. 先考虑暴力

依次枚举前缀和后缀，再用双指针判断其是否为回文 。
一共有 \(n\) 个前缀和 \(n\) 个后缀，双指针判断为 \(O(n)\) 复杂度，总复杂度为 \(O(n^3)\) 。预计得分 30 分。

2. 优化判断

由于字符串是固定的，可以预处理其哈希前缀和后缀，
再按前缀和后缀拼接后的中心分成前后两部分，合并哈希值，判断是否相等。
合并的具体方法可以参考 P4503 [CTSC2014] 企鹅 QQ 和 P6739 [BalticOI 2014] Three Friends (Day1)
总复杂度 \(O(n^2)\) 。预计得分 60 分。

3. 正解

由回文串，容易想到 manacher 算法。由样例 aababa 推测，拼接后的回文串可能含原字符串的回文子串。令前缀为 \(S_{[1 ,l_1]}\) ，后缀为 \(S[n-l_2+1,n]\) ，考虑拼接后回文中心位置。

1、 \(l_1=l_2\)

此时回文中心在前后缀之间。判断前后缀的哈希值是否相等即可。

2. \(l_1\neq l_2\)

此时回文中心在前缀或后缀中。下面以在前缀为例。如图

在跑 manacher 时,得到最长以 \(C\) 为中心的最长回文子串为 \([L,R]\) 如果取前缀 \([1 \ldots R]\) 和一个比它短的后缀，则回文中心一定在 \(C\) 处。此时只需要两个橘色部分相等即可。
而如果我只要该回文子串的部分，如 \([L' \ldots R']\) ,则需要 \([1 \ldots L']\) 有对应的后缀，条件更严格，且拼出的回文串长度与取 \([1 \ldots R]\) 一定相同。故不需要考虑。
所以我们只需要考虑以每个位置为回文中心的最长回文子串，用哈希表存初所有前缀和后缀哈希值来判断即可，复杂度 \(O(n)\) 。
需要注意来跑 manacher 的处理过的串与与原串的对应关系，详见代码

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+100;
const ull mod=3326955323;
int n,k;
char a[N];
char s[N<<1];
int p[N<<1];
ull base1,base2;
ull p1[N],p2[N];
ull fh1[N],fh2[N],th1[N],th2[N];
unordered_set<ull> ff,tt;
int ans=0;
void init(){
	base1=(rand()%100+30)|1;
	base2=(rand()%100+40);
	p1[0]=p2[0]=1;
	for(int i=1;i<=n;i++){ 
		p1[i]=p1[i-1]*base1;
		p2[i]=p2[i-1]*base2%mod;
	}
	ull tmp=0;
	ff.insert(0);
	tt.insert(0);//注意空串 
	for(int i=1;i<=n;i++){
		fh1[i]=fh1[i-1]*base1+a[i]-'a'+1;
		fh2[i]=(fh2[i-1]*base2+a[i]-'a'+1)%mod;
		ff.insert(fh1[i]*mod+fh2[i]);
		//由于unordered_set不能用pair，所以将两个哈希值哈希成一个值 
	}
	for(int i=n;i>=1;i--){
		th1[i]=th1[i+1]*base1+a[i]-'a'+1;
		th2[i]=(th2[i+1]*base2+a[i]-'a'+1)%mod;
		tmp=th1[i]*mod+th2[i];
		tt.insert(tmp);
		if(ff.count(tmp)){
			ans=max(ans,(n-i+1)*2);//中心在前缀和后缀之间的情况 
		}
	}
	//注意下标 
	s[k++]='&';//0
	s[k++]='#';//1
	for(int i=1;i<=n;i++){//1 2 3 ...
		s[k++]=a[i];//2*i   2 4 6 ...
		s[k++]='#'; //2*i+1 3 5 7 ...
	}
	s[k++]='$';
}
int main(){
	scanf("%s",a+1);
	n=strlen(a+1);
	init();
	int r=0,c=0;
	for(int i=1;i<k-1;i++){
		if(i<r) p[i]=min(p[(c<<1)-i],r-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		if(r<i+p[i]){
			r=i+p[i];
			c=i;
		}
//		cout<<i<<' '<<s[i]<<":"<<p[i]<<endl;
		if(s[i]=='#'&&p[i]==1) continue;//在原串无对应 
		int t;
		t=i-p[i]+1;
		(t+=1)>>=1;//这部分可以手推以下，比较容易 
//		cout<<"\t"<<t<<" "<<a[t]<<" "<<p[i]+t*2-3<<endl;
		if(tt.count(fh1[t-1]*mod+fh2[t-1])){
			ans=max(ans,p[i]+t*2-3); 
		} 
		t=i+p[i]-1;
		t>>=1;
//		cout<<"\t"<<t<<" "<<a[t]<<" "<<p[i]-1+(n-t)*2<<endl;
		if(ff.count(th1[t+1]*mod+th2[t+1])){
			ans=max(ans,p[i]-1+(n-t)*2);
		}
	}
	printf("%d",ans);
	return 0;
}