总时间限制: 

10000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

5120000kB

描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

回文就是正反读都是一样的字符串,如aba, abba等

 

 

输入

一个文件一组数据
每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
字符串长度len <= 110000

输出

一个整数x,表示该字符串中所包含的最长回文长度.

样例输入

aaaa-------------//忽视 分割线 下同abab

样例输出

4-------------3

 1 /* 2     裸的manache考虑三种情况  3 */ 4 #include<cstdio> 5 #include<cstring> 6 #include<iostream> 7 #define MAXN 110010 8  9 using namespace std;10 11 char s[MAXN];12 13 int L,l,ans;14 15 int t[MAXN*3],len[MAXN*3];16 17 inline void init() {18     t[l++]=‘$‘;19     t[l++]=‘#‘;20     for(int i=0;i<L;i++) {21         t[l++]=s[i];22         t[l++]=‘#‘;23     }24     t[l]=0;25     return;26 }27 28 inline void manache(){29     int p=0,p0=0;30     for(int i=1;i<=l;i++) {31         if(p>i) len[i]=min(len[2*p0-i],p-i);32         else len[i]=1;33         while(t[i-len[i]]==t[i+len[i]]) len[i]++;34         if(len[i]+i>p) {35             p=len[i]+i;36             p0=i;37         }38         ans=max(ans,len[i]-1);39     }40     return;41 }42 43 int main () {44     while(cin>>s) {45         L=l=ans=0;46         L=strlen(s);47         if(!L) break;48         init();49         manache();50         printf("%d\n",ans);51     }52     return 0;53 }

代码

 

【2012.07.11】最长回文 --马拉车算法