首页 > 代码库 > 最长回文

最长回文

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 }
View Code