本文主要是介绍Codeforces Beta Round #7--D. Palindrome Degree（hash），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
String s of length n is called k-palindrome, if it is a palindrome itself, and its prefix and suffix of length 
are (k - 1)-palindromes. By definition, any string (even empty) is 0-palindrome.
Let's call the palindrome degree of string s such a maximum number k, for which s is k-palindrome. For example, "abaaba" has degree equals to 3.
You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.
The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed5·106. The string is case-sensitive.
Output the only number — the sum of the polindrome degrees of all the string's prefixes.
a2A
1
abacaba
6
哈希一下，从左向右和从右向左的哈希值是一样的话，那么该串是回文串，所以求出从开头到第i个字符是不是回文串
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
#define Mod (LL)(1e9+7)
char str[6000000] ;
int dp[6000000] ;
int main()
{
LL ans , i , l , p , q , temp ;
while( gets(str) != 0 ) {
memset(dp,0,sizeof(dp)) ;
l = strlen(str) ;
if( l == 0 ) {
printf("0\n") ;
continue ;
}
dp[0] = 1 ;
ans = 1 ;
p = q = str[0] ;
temp = 1 ;
for(i = 1 ; i < l ; i++) {
p = (p*131+str[i]) % Mod ;
temp = (temp*131) % Mod ;
q = (str[i]*temp + q) % Mod ;
if( p == q ) {
dp[i] = dp[(i-1)/2] + 1 ;
ans += dp[i] ;
}
}
printf("%I64d\n", ans) ;
}
return 0 ;
}
这篇关于Codeforces Beta Round #7--D. Palindrome Degree（hash）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
