hdu 3068(最长回文子串O(n))

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3068

感觉这篇博客写的不错：

http://www.felix021.com/blog/read.php?2040

我就直接上代码了。。。

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int N=110010;
 4 using namespace std;
 5 int len;
 6 int p[N<<1];
 7 char s[N],str[N<<1];
 8 //数组p[i]来记录以字符str[i]为中心的最长回文子串向左（或向右）（包括str[i])的长度
 9 //id表示最大回文子串中心的位置
10 //mx则为id+p[id]，也就是最大回文子串的边界
11 
12 //最长回文子串O(n)求法
13 void Manacher(){
14     int id,mx=0;
15     for(int i=1;i<len;i++){
16         if(mx>i){
17             p[i]=min(p[(id<<1)-i],mx-i);
18         }else
19             p[i]=1;
20         for(;str[i+p[i]]==str[i-p[i]];p[i]++);
21         if(p[i]+i>mx){
22             mx=p[i]+i;
23             id=i;
24         }
25     }
26 }
27 
28 int main(){
29     while(~scanf("%s",s)){
30         len=strlen(s);
31         str[0]='$';
32         str[1]='#';
33         for(int i=0;i<len;i++){
34             str[(i<<1)+2]=s[i];
35             str[(i<<1)+3]='#';
36         }
37         len=(len<<1)+2;
38         str[len]='\0';
39         Manacher();
40         int ans=-1;
41         for(int i=0;i<len;i++){
42             ans=max(ans,p[i]);
43         }
44         printf("%d\n",ans-1);
45     }
46     return 0;
47 }