hdu 3068 最长回文

最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6336 Accepted Submission(s): 2197

Problem Description

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa 

abab

Sample Output

4

3

Source

2009 Multi-University Training Contest 16 - Host by NIT

这一道题，是一道遗留下来没有做的题目。

听说线性的算法，确实很厉害。

参考博客：http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

要仔细思考。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 char a[110011];
 8 char str[220022];
 9 int  p[220022];
10 int Min(int x,int y)
11 {
12     return x>y? y:x;
13 }
14 void solve(int n)
15 {
16     int i,j,mx=0,id;
17     for(i=0;i<=n;i++)
18         p[i]=0;
19     for(i=1;i<=n;i++)
20     {
21         if(mx>i)
22             p[i]=Min(mx-i,p[id*2-i]);
23         else p[i]=1;
24         for(;i-p[i]>=1 && i+p[i]<=n && str[i+p[i]]==str[i-p[i]];p[i]++);
25 
26         if(p[i]+i>mx)
27         {
28             mx=p[i]+i;
29             id=i;
30         }
31     }
32     for(j=0,i=1;i<=n;i++)
33         if(j<p[i])
34             j=p[i];
35     printf("%d
",j-1);
36 }
37 int main()
38 {
39     int i,len;
40     while(scanf("%s",a+1)>0)
41     {
42         len=strlen(a+1);
43         len=len*2+1;
44         for(i=1;i<=len;i++)
45         {
46             str[i]='#';
47             i++;
48             str[i]=a[i/2];
49         }
50         solve(len);getchar();
51     }
52     return 0;
53 }