题目描述
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
字符串长度为n
输入输出格式
输入格式：
一行小写英文字符a,b,c...y,z组成的字符串S
输出格式：
一个整数表示答案
输入输出样例
说明
字符串长度len <= 11000000
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 #define maxn 22000006
6 using namespace std;
7 int p[maxn],ans=-666,cnt=0;
8 char s[maxn],c;
9 int main(){
10 s[0]='@';
11 while(1){
12 c=getchar();
13 if(c==EOF||c=='\n') break;
14 if(c>='a'&&c<='z'){
15 s[++cnt]='#';
16 s[++cnt]=c;
17 }
18 }
19 s[++cnt]='#';
20 int mx=0,id=0;
21 for(int i=1;i<=cnt;i++){
22 p[i]=(mx>i?min(p[2*id-i],mx-i):1);
23 while(s[i-p[i]]==s[i+p[i]]) p[i]++;
24 if(i+p[i]>mx){
25 mx=i+p[i];
26 id=i;
27 }
28 ans=max(ans,p[i]);
29 }
30 printf("%d",ans-1);
31 return 0;
32 }
推荐学习blog：http://blog.csdn.net/dyx404514/article/details/42061017