本文主要是介绍hdu3068--最长回文(Manacer算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最长回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9418 Accepted Submission(s): 3238
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa abab
Sample Output
4 3
原字符串的回文串的长度 == p[i]-1
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define maxn 310000
int 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) ;
else
p[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 ;
}
这篇关于hdu3068--最长回文(Manacer算法)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
