CF7D.Palindrome Degree

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.

回文度

题目描述

前置知识：一个字符串与这个字符串反转后相等，则这个字符串是一个回文字符串。

一个长度为n的字符串s叫做k-palindrome当这个字符串是一个回文字符串。与此同时，这个字符串的长度为$\lceil n/2 \rceil$被称之为$k-1$-palindromes。根据定义，任何字符串（包括但不限于空字符串）也是$0$-palindrome。

一个字符串的回文度是一个字符串中最长的回文字串的长度。例如字符串”abaabc”的度即位$3$。

你的任务是找出这个字符串的所有前缀的回文度之和。

感谢Macw提供翻译

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.

输入一行一个长度不超过$5*10^6$的字符串。保证字符串仅包括拉丁大小写字符以及数字字符。该字符串是大小写敏感的。

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

输出一行一个整数，表示输入字符串的所有前缀的回文度之和。

请注意，本题的空间限制为256MB，是默认空间限制的两倍