首页 > 代码库 > 最长回文
最长回文
hdu3068:http://acm.hdu.edu.cn/showproblem.php?pid=3068
题意:给你一个字符串,求最长的回文串的长度。
题解:第一次,接触Manacher算法,这是一个模板题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define M 800050 6 using namespace std; 7 char str1[M],str[M*2]; 8 int rad[M]; 9 void Manacher(int *rad, char *str,int n){10 int i,mx=0,id;11 for(int i=1;i<n;i++){12 if(mx>i){13 rad[i]=min(rad[2*id-i],mx-i);14 }15 else rad[i]=1;16 for(;str[i+rad[i]]==str[i-rad[i]];rad[i]++){17 if(rad[i]+i>mx){18 mx=rad[i]+i;19 id=i;20 }21 }22 }23 }24 int main(){25 int i,ans,cas=1;26 while(~scanf("%s",str1)){27 int nn=strlen(str1);28 int n=nn*2+2;29 str[0]=‘$‘;30 memset(rad,0,sizeof(rad));31 for(i=0;i<=nn;i++){32 str[2*i+1]=‘#‘;33 str[2*i+2]=str1[i];34 }35 Manacher(rad,str,n);36 ans=1;37 for(int i=0;i<n;i++)38 ans=max(ans,rad[i]);39 printf("%d\n",ans-1);40 }41 return 0;42 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。