第二饭堂

题目描述:

由于一饭班长表示各种鸭梨，美丽的纪中决定历史性地启用第二饭堂。

    而部分领导觉得，二饭依山傍水，环境优美，未免有不和谐的事情（你懂的）发生，决定到二饭巡视同学们用餐时的就座情况。

    为了应付这一情况，同学们决定联合起来“布阵”。

    方便起见，同学们已经把座位情况抽象成一个长度为n的仅含数字及字母的字符串，他们想请你帮忙算算这个字符串的和谐程度。

已知一个字符串被称为k-回文串的充要条件是它自身是回文串，并且它长为⌊n/2⌋（下取整）的前缀和后缀是（k-1）-回文串。根据定义，任意字符串（包括空串）都是0-回文串。

一个字符串的回文度数就是这个字符串的k的最大值。

而对于一个给定的字符串，它的和谐程度就是其所有前缀的回文度数之和。

你的任务就是算出这个和谐程度具体是多少。

输入格式:

一行一个仅包含数字和字母的字符串。

输出格式:

一行一个整数表示这个字符串的和谐高度。

样例输入:

abacaba

样例输出:

6

提示:

【数据规模】

    对于30%的数据字符串长度不超过1000

    对于70%的数据字符串长度不超过100000

    对于100%的数据字符串长度不超过5000000

时间限制: 1000ms
空间限制: 256MB

---