可能还是非常板子的 \(Manacher\)
还是先跑一遍 \(Manacher\) 处理出来所有的回文半径 \(r[i]\)
由于我们要找的答案是两个回文串拼了起来, 所以我们考虑枚举中间这个拼接处
所以我们要找到每一个 \(i\), 其左边能够到达 \(i\) 的和右边能到达 \(i\) 的最大的回文半径
显然并不能直接使用 \(i+r[i]\) 和 \(i-r[i]\) 因为回文半径可以是比 \(r[i]\) 小的, 用小的回文半径可以拼出更大的双回文串
显然如果 \(i+r[i]-1\) 也是可以使用 \(i\) 为中心的回文半径的, 只不过回文半径长度是 \(r[i]-1\)
\(i+r[i]-2\) 同理, 是 \(r[i]-2\)
所以我们可以直接处理出一个后缀最大值, 每次传递的时候 \(beh[i]=max(beh[i],beh[i+1]-1)\) 也就是让上一个回文延续过来只不过长度减少了 \(1\)
\(i-r[i]\) 同理
代码
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #define re register
- #define maxn 200005
- #define LL long long
- #define min(a,b) ((a)<(b)?(a):(b))
- #define max(a,b) ((a)>(b)?(a):(b))
- inline int read()
- {
- char c=getchar();
- int x=0;
- while(c<'0'||c>'9') c=getchar();
- while(c>='0'&&c<='9')
- x=(x<<3)+(x<<1)+c-48,c=getchar();
- return x;
- }
- char S[maxn<<1];
- int n;
- int r[maxn<<1];
- int pre[maxn<<1],beh[maxn<<1];
- int main()
- {
- scanf("%s",S+1);
- n=strlen(S+1)<<1;
- for(re int i=n-1;i>1;i-=2) S[i]=S[(i>>1)+1];
- for(re int i=n;i;i-=2) S[i]=0;
- int mid=1,R=1;
- for(re int i=1;i<=n;i++)
- {
- if(i<=R) r[i]=min(r[(mid<<1)-i],R-i);
- for(re int j=r[i]+1;j<=i&&j+i<=n&&S[i+j]==S[i-j];j++) r[i]=j;
- if(i+r[i]>R) mid=i,R=i+r[i];
- }
- for(re int i=1;i<=n;i++)
- pre[i-r[i]]=max(pre[i-r[i]],r[i]),beh[i+r[i]]=max(beh[i+r[i]],r[i]);
- for(re int i=1;i<=n;i++) pre[i]=max(pre[i],pre[i-1]-1);
- for(re int i=n;i;i--) beh[i]=max(beh[i+1]-1,beh[i]);
- int ans=0;
- for(re int i=1;i<=n;i++)
- if(pre[i]&&beh[i])ans=max(ans,pre[i]+beh[i]);
- std::cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2905155.html