Problem1435--PIPI的字符串问题Ⅷ

1435: PIPI的字符串问题Ⅷ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 185  Solved: 60
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI研究了多年字符串后发现回文串是字符串中最优雅的一种存在了。所以PIPI发明了一种指标叫优雅度的指标来衡量一个字符串的优雅程度。优雅度定义如下:
1.空串和非回文串的优雅度为0。
2.一个长度为len的回文串的优雅度为,其长度为len/2(向下取整)的前缀和后缀的优雅度+1.
例如串"baabbaab"的优雅度为2,“babbab”的优雅度为3.
现在PIPI有一个长度为n的字符串,请你求出这个字符串的每一个前缀的优雅度的总和。

Input

第一行为一个整数n,表示串长。(n<=1e6)
第二行给出一个字符串,仅包含大写、小写字母以及数字。

Output

输出一个数字,表示答案。

Sample Input

4
ACWA

Sample Output

1

Source/Category

中等