Codeforces Beta Round #7--D. Palindrome Degree（Manacer）

本文主要是介绍Codeforces Beta Round #7--D. Palindrome Degree（Manacer），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://blog.csdn.net/winddreams/article/details/44218961

求出每个点为中心的最长字符串，判断该串是不是从开头的回文串。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int p[12000000] , dp[6000000];
char s[12000000] , str[12000000] ;
int init() {
int i , j , l ;
l = strlen(s) ;
str[0] = '&' ;
for(i = 0 , j = 1 ; i < l ; i++) {
str[j++] = '#' ;
str[j++] = s[i] ;
}
str[j++] = '#' ;
str[j] = '\0' ;
return j ;
}
void Manacer(int l) {
int i , max1 = 0 , id ;
p[0] = 0 ;
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 ;
}
//printf("%d ", p[i]) ;
}
//printf("\n") ;
}
int main() {
int i , j , l , x , ans = 0 ;
scanf("%s", s) ;
l = init() ;
Manacer(l) ;
memset(dp,0,sizeof(dp)) ;
for(i = 2 ; i < l/2+1 ; i++) {
if( i%2 == 1 && i/2 == (p[i]-1)/2 ) {
x = p[i] - 1 ;
dp[x] = dp[x/2] + 1 ;
ans += dp[x] ;
}
else if( i%2 == 0 && p[i] == i ) {
x = p[i] - 1 ;
dp[x] = dp[x/2] + 1 ;
ans += dp[x] ;
}
}
printf("%d\n", ans) ;
}

 

这篇关于Codeforces Beta Round #7--D. Palindrome Degree（Manacer）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---