题解 P4555 【[国家集训队]最长双回文串】

### **题目描述** 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。 输入长度为$n$的串$S$,求$S$的最长双回文子串$T$ ,即可将$T$分为两部分$X$,$Y$, $($|X|$,$|Y|$\geq$1)且 $X$ 和 $Y$ 都是回文串。 ## **分析** 首先给出**双回文串定义**: 双回文串$A$是指一个可以被拆分成两个部分(B和C)的字符串 $A=B+C$, 且$B$和$C$都是回文串的串, **A自己本身可以不是回文串**. 看到回文很容易想到$manacher$算法 ~~其实正解就是manacher (⊙o⊙)…~~ 我相信大家都理解如何去处理字符串的奇偶,所以不再赘述~~ 如果不会$manacher$还是先去敲板子-->[manacher](https://www.luogu.org/problemnew/show/P3805) ### 过程: 因为**双回文串是可以拼接得到**的, 所以我们可以预先处理出来数组$RL[i]$ (即**代表以$i$为对称轴的最大回文半径**) 然后我们可以定义这么两个东西 >1:$l[i]$代表$i$位置所在回文串中中心位置最左端的位置 >2:$r[i]$代表$i$位置所在回文串中中心位置最右端的位置 我们可以算出来这两个个东西。 因此**通过左右拼接就可以得到我们的双回文串**了 ## UPD: 2018.09.29. 感谢[_ConveX](https://www.luogu.org/space/show?uid=86416)指出一个天大的错误. 1.修改了$l$数组与$r$数组的定义. 2.并修改了部分代码,大家看着应该会舒服些 (可能排版不太好,请~~揍我~~谅解) ------------------ 代码------------------ ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int #define N 100010 using namespace std; char s[N<<1],ch[N]; int MaxRight,center,len; int RL[N<<1],l[N<<1],r[N<<1]; int pos,ans; int main() { cin>>ch; len=strlen(ch); for(RI i=0;i<len;i++)s[2*i+1]=ch[i]; len=2*len+1;//这里不要忘记变化长度！ RL[0]=1; for(RI i=1;i<len;i++) { if(i<=MaxRight) RL[i]=min(MaxRight-i,RL[2*center-i]); else RL[i]=1; while(i-RL[i]>=0&&RL[i]+i<len&&s[i+RL[i]]==s[i-RL[i]]) ++RL[i]; if(i+RL[i]-1>MaxRight) MaxRight=i+RL[i]-1,center=i;//注意更新操作 } for(RI i=0;i<len;i++) for(;pos<=i+RL[i]-1;pos++) l[pos]=i;//概念和上面讲的一样 pos=len; for(RI i=len-1;i>=0;i--) for(;pos>=i-RL[i]+1;pos--) r[pos]=i;//概念同上面讲的一样 for(RI i=0;i<len;i++) ans=max(ans,r[i]-l[i]);//为了保险 ,貌似可以直接减 emmm cout<<ans; } ``` 如果哪里写的~~不~~好 请私信我emmm