题意：双倍回文，他本身是一个回文串，他的长度必须是偶数，其左右两半字符串也必须是偶数回文串，求一个字符串的最长双倍回文长度
题解：
双倍回文必须是 # 为中心，否则回文串长度不可能是偶数。用Manacher算法计算出m每个以 # 为中心的最长回文串长度，在计算过程中，边扩展，边更新最长双倍回文串长度
满足双倍回文串的条件：
1.(p[i]-1)%4==0（即回文串的长度是4的倍数）
2.如何判断回文串的左右两半也是回文串？ 回文串的回文中心是i 回文串的回文半径是p[i]（奇数） 所以，左半串的回文中心就是 i-p[i]/2 如果满足 p[i-p[i]/2]>p[i] （即左回文串的回文半径大于左回文串中心到回文串中心的距离）则满足回文串的左半部分是回文串
因为对称 所以右半部份也是
3.以 # 为中心
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 5 char s[maxn],str[maxn]; 6 int l1,l2,p[maxn],ans; 7 8 void init() 9 { 10 str[0]=‘$‘; 11 str[1]=‘#‘; 12 for(int i=0;i<l1;i++) 13 { 14 str[i*2+2]=s[i]; 15 str[i*2+3]=‘#‘; 16 } 17 l2=l1*2+2; 18 str[l2]=‘*‘; 19 } 20 int manacher() 21 { 22 int id=0,mx=0,ans=0; 23 for(int i=1;i<l2;i++) 24 { 25 if(mx>i)p[i]=min(p[2*id-i],mx-i); 26 else p[i]=1; 27 for(;str[i+p[i]]==str[i-p[i]];) 28 { 29 p[i]++; 30 if(str[i]==‘#‘ && (p[i]-1)%4==0 && p[i-p[i]/2]>p[i]/2)ans=max(ans,p[i]-1); 31 } 32 if(p[i]+i>mx) 33 { 34 mx=p[i]+i; 35 id=i; 36 } 37 } 38 return ans; 39 } 40 int main() 41 { 42 43 scanf("%d",&l1); 44 scanf("%s",s); 45 l1=strlen(s); 46 init(); 47 48 printf("%d\n",manacher()); 49 return 0; 50 }
原文：https://www.cnblogs.com/j666/p/11519866.html
