Palindrome Degree

题意翻译

一个长度为 $n$ 的字符串 $s$ 被叫做 $k$ 阶级回文串，当且仅当它本身是一个回文串，而且它长度为 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 的前缀和后缀都是 $k-1$ 阶级回文串。任何一个字符串（包括空字符串）都至少是 $0$ 阶级字符串。举例来说，`abaaba` 是 $3$ 阶级字符串。 现在给定一个字符串，请求出其所有前缀的的阶级之和。 字符串长度 $\leq 5\times10^6$

题目描述

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 exceed $ 5·10^{6} $ . The string is case-sensitive.

输出格式

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

输入输出样例

输入样例 #1

a2A

输出样例 #1

1

输入样例 #2

abacaba

输出样例 #2

6

题意翻译

一个长度为 $n$ 的字符串 $s$ 被叫做 $k$ 阶级回文串，当且仅当它本身是一个回文串，而且它长度为 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 的前缀和后缀都是 $k-1$ 阶级回文串。任何一个字符串（包括空字符串）都至少是 $0$ 阶级字符串。举例来说，`abaaba` 是 $3$ 阶级字符串。 现在给定一个字符串，请求出其所有前缀的的阶级之和。 字符串长度 $\leq 5\times10^6$