题解 P4287 【[SHOI2011]双倍回文】

吾王美如画 · 2019-04-07 22:44:32 · 题解

（难得有次直接讲题

• 看完题之后，注意题中要求的是WWrWWr这样的形势，也就是把一个串翻转几次，而不是单纯的两个回文子串。

• 于是，我们得知了几个有趣的特点

  1. 回文子串的中心必须在‘#’上
  2. 左右两个回文子串相等，且整个子串是回文子串

• 根据以上的特点，当我们在求半径数组rad时，以目前位置i为右子串的中心，而整个子串的中心mid可以是i-rad[i]+1到i之间的任意一点，也就任意是以i为中心的回文子串的右边界。所以这些点都可以保证右边是回文子串。

• 接着找到i点对应mid的对称点l，也就是左子串的中心点，如果l+rad[l]-1>mid，也就是mid为以l为中心的回文子串的左边界。

• 最后，为了保证左子串和右子串相等，我们要确定，这两个子串是否被mid的回文子串包含了。

ps：之前有大佬在题解里说了，在枚举mid的时候，并不需要把i-rad[i]+1到i全部找一遍，只用到i-rad[i]+7就ok（没有为什么，因为这是试出来的

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm> 
#define MAXN 4100000
using namespace std;
int rad[MAXN],n;
char s[MAXN],ch[MAXN];
int mr=-1,c;
void find(int x,int y){
    int i=y;
    for(;(x-i)>=0&&(x+i)<=2*n;i++){
        if (s[x-i]!=s[x+i])break;
    }
    rad[x]=i;
}
int main(){
    s[0]='#';
    cin>>n;
    cin>>ch+1;
    for(int i=1;i<=n;i++){
        s[2*i-1]=ch[i];
        s[2*i]='#'; 
    }
    int ans=0;
    memset(rad,0,sizeof(rad));
    for(int i=0;i<=n*2;i++){
        if (i&1)continue;
        if (i>mr) find(i,0);
        else {
            int cl,p2,pl;
            cl=c-(mr-c);
            p2=c-(i-c);
            pl=p2-rad[p2]+1;
            if (pl>cl){
                rad[i]=rad[p2];
            }
            else if (pl<cl){
                rad[i]=mr-i+1;
            }
            else {
                find(i,mr-i+1);
            }
        }
        if (i+rad[i]-1>mr){
            mr=i+rad[i]-1;
            c=i;
        }
        int mid,l;
        for(int j=0;j<=6;j++){
             mid=i-rad[i]+1+j;
             l=mid-(i-mid);
             if (l<0)continue;
             if (l+rad[l]-1>=mid&&mid+rad[mid]-1>=i)ans=max(ans,(rad[i]-j)*2-2);
        } 
    }
    cout<<ans<<endl;
    return 0;
}