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

· · 题解

楼下 or 楼上的dalao对不起，现在我成为最快且最短的一份代码了。

这道题显然不是什么<=6特判的乱搞，其实也不应该是O(n * a(n))的并查集，正确的做法是线性的：考虑所有O(n)个本质不同的回文串，对每个回文串都可以O(1)判断。具体实现中,只需要在manacher中mx更新时,判断所有新出现的回文串的前一半是否为回文串即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[1000010]={'?'};
int p[1000010],n,ans;
void manacher(char *s,int n){
    for(int c=0,mx=0,i=1;i<=n;i++){
        p[i]=i<mx?min(p[2*c-i],mx-i):1;
        while(s[i+p[i]]==s[i-p[i]])++p[i];
        if(i+p[i]>mx){
            if(i&1)for(int j=max(mx,i+4);j<i+p[i];j++)
                if(!(j-i&3) && p[i-(j-i)/2]>(j-i)/2)ans=max(ans,j-i);
            mx=i+p[i],c=i;
        }
    }
}
int main(){
    scanf("%d %s",&n,s+1);
    for(int i=n;i;i--)s[i*2+1]='#',s[i*2]=s[i];s[1]='#';
    manacher(s,2*n+1);
    printf("%d\n",ans);
    return 0;
}