链接
http://codeforces.com/contest/1326/problem/D2
题意
$a$ 是 $s$ 的前缀，$b$ 是 $s$ 的后缀
使 $a+b$ 是可以找到的最大的回文串
$a$ 或 $b$ 可以是空串
思路
找出最大长度 $k$ 使 $s[0,k-1]+s[len(s)-k,len(s)-1]$ 是回文串
再用 Manacher 算法求出 $s[k,len(s)-k-1]$ 中以 $s[k]$ 为右端的的最大回文串和以 $s[len(s)-k-1]$为左端的最大回文串（计算出 $len[i]$ 后，判断以 $i$ 为中心的最大回文串的左端和右端即可）
把较大的那个回文串加在开始找到的长度为 $2*k$ 的回文串中间即是最大答案
注意：当一开始找长度 $k$ 时 $k-1\ge len(s)-k$ 时，$s$ 本身就是一个回文串
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s[N],str[N*2];
int len[N*2];
pair<int,int> Manacher(int l,int r) {
str[0]='$';
int k=0;
for(int i=l;i<=r;i++) str[++k]='#',str[++k]=s[i];
str[++k]='#';
len[0]=0;
int id=0,mx=0;
int mxl=0,mxr=0;
for(int i=1;i<=k;i++) {
len[i]=i<mx?min(mx-i,len[2*id-i]):1;
while(i-len[i]>=0&&i+len[i]<=k&&str[i-len[i]]==str[i+len[i]]) ++len[i];
if(len[i]+i>mx)mx=len[i]+i,id=i;
if(len[i]==i) {
if(len[i]-1>mxl) mxl=len[i]-1;
}
else if(len[i]==k-i+1) {
if(len[i]-1>mxr) mxr=len[i]-1;
}
}
if(mxl>mxr) return make_pair(0,mxl);
else return make_pair(1,mxr);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;
while(T--) {
cin>>s;
int l=0,r=strlen(s)-1;
while(l<r&&s[l]==s[r]) l++,r--;
if(l>=r){cout<<s<<endl;continue;}
pair<int,int> res=Manacher(l,r);
for(int i=0;i<l;i++) cout<<s[i];
if(res.first==0) for(int i=l;i<=l+res.second-1;i++) cout<<s[i];
else if(res.first==1) for(int i=r-res.second+1;i<=r;i++) cout<<s[i];
for(int i=l-1;i>=0;i--) cout<<s[i];
cout<<endl;
}
return 0;
}
|