SHOI2011-双倍回文

记字符串$w$的倒置为$w^R$。例如$(abcd)^R=dcba$，$(abba)^R=abba$。

对字符串x，如果$x$满足$x^R=x$，则称之为回文；例如abba是一个回文，而abed不是。

如果x能够写成的$ww^Rww^R$形式，则称它是一个“双倍回文”。换句话说，若要$x$是双倍回文，它的长度必须是$4$的倍数，而且$x$，$x$的前半部分，$x$的后半部分都要是回文。例如$abbaabba$是一个双倍回文，而$abaaba$不是，因为它的长度不是4的倍数。

$x$的子串是指在$x$中连续的一段字符所组成的字符串。例如$be$是$abed$的子串，而$ac$不是。

$x$的回文子串，就是指满足回文性质的$x$的子串。

$x$的双倍回文子串，就是指满足双倍回文性质的$x$的子串。

你的任务是，对于给定的字符串，计算它的最长双倍回文子串的长度。

思路

感觉是一个对于理解 $\mathrm{Manacher}$ 算法的好题。

直接在进行 $\mathrm{Manacher}$ 的过程中，判断所有新出现的回文串的前一半是否为回文串即可。

巧妙利用了 $R$ 的特性，每个点只会被判断一次，时间复杂度 $O(n)$ 。

代码

#include<bits/stdc++.h>
#define N 500010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,P[N<<1],ans=0;
char a[N],s[N<<1];

void change() {
    int m=0;
    s[m++]='$',s[m++]='#';
    for(int i=0;i<n;i++) s[m++]=a[i],s[m++]='#';
    s[m++]='&';
    n=m;
}

void Manacher() {
    int R=0,C;
    for(int i=1;i<n;i++) {
        if(i<R) P[i]=min(P[(C<<1)-i],R-i);
        else P[i]=1;
        while(s[i+P[i]]==s[i-P[i]]) {					//这个 while 循环值得深思
            P[i]++;
            if(R<i+P[i]&&(i&1)&&(P[i]-1)%4==0) if(P[i-(P[i]-1)/2]-1>=(P[i]-1)/2) ans=max(ans,P[i]-1);
        }
        if(i+P[i]>R) {
            R=i+P[i];
            C=i;
        }
    }
}

int main() {
    n=read();
    scanf("%s",a);
    change();
    Manacher();    
    printf("%d\n",ans);
    system("pause");
    return 0;
}