HDU 3068 最长回文 - c++编程基础

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

关于最长回文串问题，可以参考：

http://my.oschina.net/pathenon/blog/63575

http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063. html

#include  
#include  
#include  
using namespace std;  
#define max 110010 * 2  
char init[max]; //输入原始字符串  
char result[max]; //加入‘#’后的字符串  
int p[max];  
int n; //the length of result[];  
  
void pre()  
{  
    int len,i;  
    len = strlen(init);  
    result[0] = '$';  
    result[1] = '#';  
    for(i=0; i




 i)  
            p[i] = p[idx*2 - i] < (end-i)  p[2*idx - i]:(end-i);  
        else  
            p[i] = 1;  
        for(; result[i + p[i]]==result[i - p[i]]; p[i]++);  
        if(p[i] + i > end)  
        {  
            end = p[i] + i;  
            idx = i;  
        }  
    }  
}  
  
  
int main()  
{  
    int t,i;  
    while(scanf("%s",init) != EOF)  
    {  
        t = 0;  
        //memset(result,0,sizeof(result));  
        //memset(p,0,sizeof(p));  
        pre();  
        process();  
        for(i=2; i t)  
                t = p[i];  
        }  
        printf("%d\n",t-1);  
    }  
    return 0;  
}