Manacher || P4555 [国家集训队]最长双回文串 || BZOJ 2565: 最长双回文串

题解：就、就考察马拉车的理解

在原始马拉车的基础上多维护个P[i]、Q[i]数组，分别表示以i结尾最长回文子串的长度和以i开头的最长回文子串的长度

然后就枚举断点，只能选择#作为断点，因为#..#才是一个字符串；第一个和最后一个#不能作为断点，因为答案要求|X|、|Y|都>=1

就维护答案

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define max(a,b) ((a)>(b)?(a):(b))
 5 #define min(a,b) ((a)<(b)?(a):(b))
 6 #define re register
 7 using namespace std;
 8 const int maxn=(1e5)+50;
 9 int len,cnt,mr,mid,RL[maxn<<1],P[maxn<<1],Q[maxn<<1],ans=0,a,b,toi,j;
10 char S[maxn<<1],O[maxn];
11 inline void Manacher(){
12     mr=mid=0;
13     for(re int i=1;i<=len;i++){
14         if(i<mr)RL[i]=min(mr-i,RL[(mid<<1)-i]);
15         else RL[i]=1;
16         while(S[i-RL[i]]==S[i+RL[i]]){
17             P[i+RL[i]]=max(P[i+RL[i]],(RL[i]<<1)+1);
18             Q[i-RL[i]]=max(Q[i-RL[i]],(RL[i]<<1)+1);
19             RL[i]++;
20         }
21         if(i+RL[i]-1>mr){
22             mr=i+RL[i]-1;
23             mid=i;
24         }
25     }
26     return;
27 }
28 int main(){
29     scanf("%s",O);
30     len=strlen(O);
31     S[0]='$';
32     S[cnt=1]='#';
33     for(re int i=0;i<len;i++){
34         S[++cnt]=O[i];
35         S[++cnt]='#';
36     }
37     len=cnt;
38     Manacher();
39     for(re int i=len;i>=1;i--){
40         P[i]=max(P[i],P[i+1]-2);
41         j=len-i+1;
42         Q[j]=max(Q[j],Q[j-1]-2);
43     }
44     toi=len-2;
45     for(re int i=3;i<=toi;i++)
46         if(S[i]=='#'){
47             a=(P[i]-1)>>1;b=(Q[i]-1)>>1;
48             ans=max(ans,a+b);
49         }
50     printf("%d
",ans);
51     return 0;
52 }

By:AlenaNuna