Codeforces 7D. Palindrome Degree

Description

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.

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 exceed 5·106. The string is case-sensitive.

Output

Output the only number — the sum of the polindrome degrees of all the string’s prefixes.

Examples

input

1
a2A

output

1
1

input

1
abacaba

output

1
6

Solution

题目大意：对于一个串S（包括空串）的价值我们有如下定义：

1.如果S不是一个回文串或S是一个空串，其价值为0；

2.如果S是一个回文串，取长度为其一半的前缀T（向下取整），则S的价值等于T的价值+1。

给定一个长为Length的串，求它所有前缀的价值总和。

Length <= 5*10^6

Manacher的简单递推。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
char str[5000005], tmp[10000005];
int mx[10000005], le[10000005], ri[10000005], T[10000005];
int n;
int main() {
	scanf("%s", str + 1);
	n = strlen(str + 1);
	for (int i = 1; i <= n; ++i) {
		tmp[i * 2 - 1] = '#';
		tmp[i * 2] = str[i];
	}
	int N = n * 2 + 1;
	tmp[N] = '#';
	tmp[N + 1] = '$';
	int pos, r = 0;
	for (int i = 1; i <= N; ++i) {
		if (r > i) mx[i] = min(r - i, mx[pos * 2 - i]);
		else mx[i] = 1;
		while (tmp[i + mx[i]] == tmp[i - mx[i]]) ++mx[i];
		if (mx[i] + i - 1 > r) {
			r = mx[i] + i - 1;
			pos = i;
		}
		le[i] = i - mx[i] + 1;
		ri[i] = i + mx[i] - 1;
	}
	for (int i = 2; i <= N; ++i) {
		if (le[i] != 1) continue;
		int pos = ri[i] / 2;
		T[pos] = T[pos / 2] + 1;
	}
	LL ans = 0;
	for (int i = 1; i <= n; ++i)
		ans += T[i];
	printf("%d", ans);
    return 0;
}