D. Palindrome Degree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Stringof lengthis called-palindromes. By definition, any string (even empty) is 0-palindrome.
Let’s call the palindrome degree of stringsuch a maximum numberk, for whichisk-palindrome. For example, "abaaba" has degree equals to3.
You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.
Input
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
Output the only number — the sum of the polindrome degrees of all the string’s prefixes.
Sample test(s)
input
a2A
output
1
input
abacaba
output
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 ;}
赚钱之道很多，但是找不到赚钱的种子，便成不了事业家。
