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

· · 题解

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。

输入长度为n的串S,求S的最长双回文子串T ,即可将T分为两部分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指出一个天大的错误.

1.修改了l数组与r数组的定义.

2.并修改了部分代码,大家看着应该会舒服些

(可能排版不太好,请揍我谅解)

------------------ 代码------------------

#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