Description
顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。
Input
一行由小写英文字母组成的字符串S。
Output
一行一个整数,表示最长双回文子串的长度。
正反各运行一次manacher,同时求出以某个位置为左/右边界的最长回文串长度,最后扫描一次每个分界点取最大值。
#include<cstdio>
#include<cstring>
char s[],s1[];
int p[],p2[];
int rx[];
int lx[];
inline int min(int a,int b){return a<b?a:b;}
inline int maxs(int&a,int b){if(a<b)a=b;}
int main(){
scanf("%s",s1);
int l=strlen(s1);
for(int i=;i<l;i++)s[i+i+]=s1[i];
l+=l;
s[]=;
s[l+]=;
int mx=,id=;
for(int i=;i<=l;i++){
if(i<mx)p[i]=min(p[(id<<)-i],mx-i);
else p[i]=;
maxs(rx[i],);
while(s[i+p[i]]==s[i-p[i]]){
if(i+p[i]<=l)maxs(rx[i+p[i]],p[i]+);
++p[i];
}
if(i+p[i]>mx){
mx=i+p[i];
id=i;
}
}
mx=id=l+;
for(int i=l;i>=;i--){
if(i>mx)p2[i]=min(p2[(id<<)-i],i-mx);
else p2[i]=;
maxs(lx[i],);
while(s[i-p2[i]]==s[i+p2[i]]){
if(i-p2[i]>=)maxs(lx[i-p2[i]],p2[i]+);
++p2[i];
}
if(i-p2[i]<mx){
mx=i-p2[i];
id=i;
}
}
int ans=;
for(int i=;i<l;i+=)maxs(ans,lx[i+]+rx[i-]);
printf("%d",ans);
return ;
}