hdu3068 最长回文 manacher

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

manacher裸题

 #include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int maxn=11e4+;
char s[maxn],t[maxn<<];
int p[maxn<<]; void manacher(){
int len=strlen(s),l=;
t[l++]='$';
t[l++]='#';
for(int i=;i<len;++i){
t[l++]=s[i];
t[l++]='#';
}
t[l]=;
int maxx=,num=;
for(int i=;i<l;++i){
p[i]=maxx>i?min(p[*num-i],maxx-i):;
while(t[i+p[i]]==t[i-p[i]])p[i]++;
if(i+p[i]>maxx){
maxx=i+p[i];
num=i;
}
}
} int main(){
while(scanf("%s",s)!=EOF){
manacher();
int l=strlen(s);
int ans=;
for(int i=;i<*l+;++i){
if(p[i]->ans)ans=p[i]-;
}
printf("%d\n",ans);
}
return ;
}
上一篇:vi 格式配置


下一篇:jQuery系列 第二章 jQuery框架使用准备