Time:2016.08.16 Author:xiaoyimi 转载注明出处谢谢
传送门 思路： woc第一次写马拉车怎么这么蛋疼啊 p[i]表示以i为中点，能向增长的最多的回文长度的一半 比如”abcba”,s[3]=’c’,p[3]=5/2=2 考虑枚举双倍回文 WWRWWR 的中点i 然后再枚举前半端 WWR 的中点j j的取值为[i-p[i]/2,i) 这样保证，如果j符合要求那么后半端 WWR 一定符合要求 因为前后端组成双倍回文 ans=max((i-j)*4) 复杂度 O(n2) 网上的优化有很多…… set,树状数组,二分答案,暴力…… 真是太神了…… 代码：
#include<cstdio> #include<iostream> #include<cstring> #define M 500010 using namespace std; int n,len; int p[M<<1]; char s[M],a[M<<1]; int fa[M]; void manacher() { int id=0,mx=0; for (int i=1;i<=len;i++) { if (mx>i) p[i]=min(p[2*id-i],mx-i); else p[i]=0; for (;a[i-p[i]]==a[i+p[i]];++p[i]); if (i+p[i]>mx) mx=i+p[i],id=i; } } int find(int x){fa[x]=(fa[x]==x?fa[x]:find(fa[x]));return fa[x];} main() { scanf("%d",&n); scanf("%s",s+1); a[0]='!'; a[++len]='#'; for (int i=1;i<=n;i++) a[++len]=s[i], a[++len]='#'; a[len+1]='?'; manacher(); for (int i=1;i<=n;i++) p[i]=(p[i<<1|1]-1)/2,fa[i]=i; fa[n+1]=n+1; int ans=0; for(int i=1;i<=n;i++) for (int j=find(max((i-p[i]/2),1));j<i;fa[j]=find(j+1),j=fa[j]) if (p[j]+j>=i) {ans=max((i-j)*4,ans);break;} printf("%d\n",ans); }