版权声明:本文为博主原创文章,未经博主同意不得转载。 https://blog.csdn.net/neng18/article/details/24269469
题意:给出一个仅仅由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等
思路:用Manacher算法
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 300010
int n,p[MAXN];
char s[MAXN],str[MAXN];
void kp(){
int i,mx=0,id;
for(i=n;str[i]!=0;i++)
str[i]=0;
for(i=1;i<n;i++){
if(mx>i)
p[i]=min(p[2*id-i],mx-i);
else
p[i]=1;
while(str[i+p[i]]==str[i-p[i]])
p[i]++;
if(p[i]+i>mx){
mx=p[i]+i;
id=i;
}
}
}
void init(){
int i,j,k;
str[0]='$';
str[1]='#';
for(i=0;i<n;i++){
str[i*2+2]=s[i];
str[i*2+3]='#';
}
n=n*2+2;
s[n]=0;
}
int main(int argc, char** argv) {
int i,ans;
while(scanf("%s",s)!=EOF){
n=strlen(s);
init();
kp();
ans=0;
for(i=0;i<n;i++)
if(p[i]>ans)
ans=p[i];
printf("%d\n",ans-1);
}
return 0;
}