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++]='&';//0s[k++]='#';//1for(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;
}