最长回文
Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 9418Accepted Submission(s): 3238
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
aaaaabab
Sample Output
43
原字符串的回文串的长度 == p[i]-1
#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;#define maxn 310000int p[maxn] ;char s[maxn] , str[maxn] ;int init() {int i = 0 , j = 0 , l = strlen(s) ;str[j++] = '$' ;while( i < l ) {str[j++] = '#' ;str[j++] = s[i] ;i++ ;}str[j++] = '#' ;str[j] = '\0' ;return j ;}void Manacer(int l) {int i , max1 = 0 , id ;for(i = 1 ; i < l ; i++) {if( max1 > i )p[i] = min(p[2*id-i],max1-i) ;elsep[i] = 1 ;while( str[i-p[i]] == str[i+p[i]] )p[i]++ ;if( p[i]+i > max1) {max1 = p[i] + i ;id = i ;}}}int main() {int max1 , i , l ;while( scanf("%s", s) != EOF ) {l = init() ;Manacer(l) ;max1 = 0 ;for(i = 1 ; i < l ; i++) {max1 = max(max1,p[i]) ;}printf("%d\n", max1-1) ;}return 0 ;}
，你必须百分之百的把自己推销给自己。
