题解 P4555 【最长双回文串】
浅色调
2018-05-25 22:16:19
### Solution:
本题$zyys$啊!~
很容易想到$manacher$,于是先打个板子看看,处理出以$i$为中心的最长回文半径$p[i]$后,就断思路了。
我首先想到的是,在每次更新$p[i]$后,分别处理出以$i$为中心的半径$p[i]$内,每个位置为开头和结尾的最长回文子串长度($manacher$结束后直接枚举断点就可以得到答案),但是这样强行又将复杂度拉到了$O(n^2)$。于是,开始断线~
后面看看巨佬们的思路,豁然**,我是真的蠢啊~
其实,将我开始的思路修改一下即可:
我们维护最长回文半径$p[i]$的同时,再分别维护两个东西,以$i$为结尾的最长回文子串的长度$ll[i]$,和以$i$为开头的最长回文子串的长度$rr[i]$。
那么很显然,因为以$i$为中心的最长回文子串长度为$p[i]-1$,所以每次更新$p[i]$后,我们只需处理出当前这个回文子串的左右边界(中间的每个点的$ll[i],rr[i]$可以在$manacher$结束后$O(n)$处理出),则$ll[i+p[i]-1]=max(ll[i+p[i]-1],p[i]-1)$(更新以$i+p[i]-1$为结尾的最长回文长度),同理$rr[i-p[i]+1]=max(rr[i-p[i]+1],p[i]-1)$。
跑完$manacher$后,我们$O(n)$递推出每个'#'为断点的$ll[i]$和$rr[i]$,其中$rr[i]$因为是$i$结尾的回文长度,所以直接顺推,每往后移一位,最长回文子串长度$-2$,于是$rr[i]=max(rr[i],rr[i-2]-2)$($i-2$是上一个'#'位置),同理$ll[i]$直接逆推,类似地$ll[i]=max(ll[i],ll[i+2]-2)$。
最后枚举每个'#'为断点,更新$ans$就$OK$了。
$\quad\;\;$欢迎来踩博客:[five20](https://www.cnblogs.com/five20/p/9090876.html)(蒟蒻写题解不易,转载请注明出处~万分感谢!)
### 代码:
```cpp
#include<bits/stdc++.h>
#define For(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define Bor(i,a,b,c) for(int (i)=(b);(i)>=(a);(i)-=(c))
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=200050;
int p[N],ll[N],ans,rr[N],mx,id,cnt;
char s[N],t[N];
int main(){
scanf("%s",t);
int len=strlen(t);
s[++cnt]='$',s[++cnt]='#';
For(i,0,len-1,1)s[++cnt]=t[i],s[++cnt]='#';
s[++cnt]='\0';
For(i,1,cnt,1){
if(i<mx)p[i]=Min(p[id*2-i],mx-i);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]])p[i]++;
if(mx<i+p[i])id=i,mx=i+p[i];
ll[i+p[i]-1]=Max(ll[i+p[i]-1],p[i]-1);
rr[i-p[i]+1]=Max(rr[i-p[i]+1],p[i]-1);
}
For(i,2,cnt,2)rr[i]=Max(rr[i],rr[i-2]-2);
Bor(i,2,cnt,2)ll[i]=Max(ll[i],ll[i+2]-2);
For(i,2,cnt,2)if(rr[i]&&ll[i])ans=Max(ans,ll[i]+rr[i]);
cout<<ans;
return 0;
}
```