← 返回题目列表

Codeforces · 7/D

D. 回文度

中文机器翻译题面 查看原题

长度为 n 的字符串 s 称为 k-回文,如果它本身是回文,并且其长度 $$\left\lfloor n/2 \right\rfloor$$ 的前缀和后缀是 (k - 1)-回文。根据定义,任何字符串(甚至是空字符串)都是 0 回文。

我们将字符串 s 的回文度称为最大数 k,其中 s 是 k-回文。例如,“abaaba”的度数等于 3。

给你一个字符串。您的任务是找到其所有前缀的回文度数之和。

输入

输入数据的第一行包含一个非空字符串,由拉丁字母和数字组成。字符串长度不超过5·106。该字符串区分大小写。

输出

输出唯一的数字——所有字符串前缀的回数度之和。

示例

输入 #1

a2A

输出 #1

1

输入 #2

abacaba

输出 #2

6