题解 BZOJ 2565 最长双回文串

求最长双回文串.
首先Manacher求回文半径p[i]。
然后求每个点最左是可以由哪一个点扩展来的left[i]。
具体就是拿个数组弄一个 i+p[i] 的后缀min。
刚开始想单调队列好像也行。
然后对于一个点以它为右回文串中心的最大双回文串长度就是i-left[i-p[i]+1].
取个max就行了。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[100005],a[210005];
int p[210005];
int l,mx,id;
int left[210005];
int mn[210005];
int main(){
scanf("%s",s+1);
for(int i=1;s[i];i++){
a[2*i]=s[i];
a[2*i+1]='#';
}
int l=strlen(s+1);
a[1]='#';
a[0]='$';
mx=-1;
for(int i=1;i<=l*2+1;i++){
if(i<mx){p[i]=min(p[id-(i-id)],mx-i);}
while(a[i+p[i]]==a[i-p[i]]) p[i]++;
if(i+p[i]>mx) mx=i+p[i],id=i;
}
memset(mn,0x3f,sizeof mn);
for(int i=1;i<=l*2;i++){
mn[i+p[i]]=min(mn[i+p[i]],i);
}
left[l*2+1]=0x3f3f3f3f;
for(int i=l*2;i>=1;i--) left[i]=min(left[i+1],mn[i]);
int ans=0;
for(int i=1;i<=l*2;i++){
ans=max(ans,i-left[i-p[i]+1]);
}
printf("%d\n",ans);
return 0;
}

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框