题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3068
题目大意:求字符串s中最长的回文子串
解题思路:manacher模板
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+; int len1,len2;
int p[N];
char s[N],str[N]; void init(){
str[]='$';
str[]='#';
for(int i=;i<len1;i++){
str[i*+]=s[i];
str[i*+]='#';
}
len2=len1*+;
str[len2]='%';
} void manacher(){
int id=,mx=;
for(int i=;i<len2;i++){
if(mx>i) p[i]=min(p[*id-i],mx-i);
else p[i]=;
while(str[i+p[i]]==str[i-p[i]])
p[i]++;
if(p[i]+i>mx){
mx=p[i]+i;
id=i;
}
}
} int main(){
while(~scanf("%s",s)){
len1=strlen(s);
init();
manacher();
int ans=;
for(int i=;i<len2;i++){
ans=max(ans,p[i]);
}
printf("%d\n",ans-);
}
return ;
}