[国家集训队]最长双回文串
感觉很迷惑，尝试使用各种数据结构但发现并不是很好处理。。。
后来发现自己是个深必，怎么就想不到递推嘞。。。
Manacher 先求出 $d(i)$，容易想到以 $i$ 为中心的最长回文串长度为 $d(i)-1$，则我们设 $datl(i-d(i)+1)=\max {d(i)-1}$，$datr(i+d(i)-1)=\max{d(i)-1}$。
然后我们知道这个肯定没有完全求出 $datl(i)$ 和 $datr(i)$ 的值，因为这个回文串缩一缩也是可以的，所以我们想办法把这些短的回文串也给搞出来。
于是就有了数据结构递推，$datr(i)=\max{datr(i-2)-2}$，$datl(i)=\max{datl(i+2)-2}$。
一个正推一个反推，最后在除了第一个和最后一个 # 的位置取最大值即可。。。
时间复杂度 $O(n)$。
代码：
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
namespace io {
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}
using io::read;using io::write;
const ll N=2e5;
ll d[N+5],datl[N+5],datr[N+5];
char a[N+5],s[N+5];
int main() {
scanf("%s",a);ll n=strlen(a);
s[0]='#';for(ll i=0;i<n;i++) {s[i*2+1]=a[i];s[i*2+2]='#';}
ll m=n*2+1;
for(ll i=0,l=0,r=-1;i<m;i++) {
ll k=(i>r)?1:min(d[l+r-i],r-i+1);
while(0<=i-k&&i+k<m&&s[i-k]==s[i+k]) k++;
d[i]=k--;if(i+k>r) {l=i-k;r=i+k;}
}
for(ll i=0;i<m;i++) {
datl[i+d[i]-1]=max(datl[i+d[i]-1],d[i]-1);
datr[i-d[i]+1]=max(datr[i-d[i]+1],d[i]-1);
}
ll ans=0;
for(ll i=0;i<m;i+=2) {
datr[i]=max(datr[i],datr[i-2]-2);
}
for(ll i=m-1;i>=0;i-=2) {
datl[i]=max(datl[i],datl[i+2]-2);
}
for(ll i=2;i<m-2;i+=2) {
ans=max(ans,datl[i]+datr[i]);
}
write(ans);
return 0;
}
|