题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2565
题意：中文题
思路：定义L[i],R[i]。表示以i为左端点/右端点时，最长回文串长度。那么答案就是L[i]+R[i]的最大值。问题转化为怎么求L[i],R[i]。我们通过用Manacher可以求出以i为中心的最长回文串半径。然后再通过暴力+剪枝的方法对于每一个i和对应的最长半径求更新L[i],R[i]。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e5+;
typedef long long int LL;
#define INF 0x3f3f3f3f
char str[MAXN],dstr[MAXN*];
int lenstr,lendstr,p[MAXN*],L[MAXN*],R[MAXN*],ans;
void manacher(){
memset(p,,sizeof(p));
memset(L,-,sizeof(L));
int id=,mx=;
for(int i=;i<lendstr;i++){
if(mx>i){
p[i]=min(p[*id-i],mx-i);
}
else{
p[i]=;
}
while(dstr[i-p[i]]==dstr[i+p[i]]){ //暴力匹配
p[i]++;
}
if(p[i]+i>mx){ //更新mx
mx=p[i]+i;
id=i;
}
}
}
void init(){ //变化原串
dstr[]='$';
dstr[]='#';
for(int i=;i<lenstr;i++){
dstr[i*+]=str[i];
dstr[i*+]='#';
}
lendstr=lenstr*+;
dstr[lendstr]='*';
}
int main()
{
while(~scanf("%s",str)){
lenstr=strlen(str);
init();
manacher();
ans=;
for(int i=;i<lendstr;i++){
p[i]--; L[i]=max(L[i],); R[i]=max(R[i],);
for(int j=p[i];j>;j--){
if(R[i+j]>=j){ //剪枝
break;
}
R[i+j]=j;
}
for(int j=p[i];j>;j--){
if(L[i-j]>=j){ //剪枝
break;
}
L[i-j]=j;
}
}
for(int i=;i<lendstr;i++){
if(L[i]>&&R[i]>){
ans=max(ans,L[i]+R[i]);
}
}
printf("%d\n",ans);
}
return ;
}
上面的代码跑了8S+。因为是暴力更新的L,R数组。所以复杂度几乎是O(n^2).考虑优化。我们可以知道在进行Manacher的时候可以知道当前已经覆盖的最远的位置mx和对应的id。那么当某个位置被mx第一次被覆盖之时,可以知道这个位置的R[i]一定是mx-id因为是第一次被覆盖到。所以一定是最长最优的。同理左边对应位置的L[i]也是。 意思就是在Manacher的过程顺便更新L[i],R[i].
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + ;
typedef long long int LL;
#define INF 0x3f3f3f3f
char str[MAXN], dstr[MAXN * ];
int lenstr, lendstr, p[MAXN * ], R[MAXN * ], L[MAXN * ], ans;
void manacher(){
memset(R, -, sizeof(R));
memset(L, -, sizeof(L));
int id = , mx = ;
for (int i = ; i<lendstr; i++){
if (mx>i){
p[i] = min(p[ * id - i], mx - i);
R[i + p[i]] = max(R[i + p[i]], p[i]);
L[i - p[i]] = max(L[i - p[i]], p[i]);
}
else{
p[i] = ;
R[i] = max(R[i], p[i]);
L[i] = max(L[i], p[i]);
}
while (dstr[i - p[i]] == dstr[i + p[i]]){ //暴力匹配
R[i + p[i]] = max(R[i + p[i]], p[i]);
L[i - p[i]] = max(L[i - p[i]], p[i]);
p[i]++;
}
if (p[i] + i>mx){
mx = p[i] + i;
id = i;
}
}
}
void init(){
dstr[] = '$';
dstr[] = '#';
for (int i = ; i<lenstr; i++){
dstr[i * + ] = str[i];
dstr[i * + ] = '#';
}
lendstr = lenstr * + ;
dstr[lendstr] = '*';
}
int main()
{
while (~scanf("%s", str)){
lenstr = strlen(str);
init();
manacher();
ans = ;
for (int i = ; i<lendstr; i++){
if (L[i]>&&R[i]>){
ans = max(ans, L[i] + R[i]);
}
}
printf("%d\n", ans);
}
return ;
}