[洛谷 202406GESP 模拟 三级] 小洛的字符串分割

题目描述

对于一个字符串 $S$,小洛定义它为 **回文** 的,当且仅当字符串 $S$ 从左往右读和从右往左读一样,例如 $\tt abcba$ 是回文的,而 $\tt abcca$ 不是。 小洛现在有一个字符串 $S$,他想将这个字符串分为若干段,段长度分别为 $1,2,3,\dots$。具体而言,他会先将第一个字符拿出来作为字符串 $S_1$,再将第 $2,3$ 个字符拿出来作为 $S_2$,再将第 $4,5,6$ 个字符拿出来作为 $S_3$,以此类推……最后若还有多余的字符,则单独作为一段。 例如说,对于字符串 $\tt aaababcaacd$,会被分为如下的五个字符串: - $S_1=\tt a$; - $S_2=\tt aa$; - $S_3=\tt bab$; - $S_4=\tt caac$; - $S_5=\tt d$; 字符串 $\tt aaababcaacd$ 分割出的 $5$ 个字符串都是回文的。 小洛想要知道,对于读入的字符串 $S$,这些被分割出来的字符串,有**多少个**是回文的呢?

输入输出格式

输入格式


输入一行,一个字符串 $S$。

输出格式


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

输入输出样例

输入样例 #1

aaababcaacd

输出样例 #1

5

输入样例 #2

abacdcaaba

输出样例 #2

2

说明

**【样例解释】** - 对于第 $1$ 组样例,已经在题面中进行表述; - 对于第 $2$ 组样例,$S_1=\tt a$,$S_2=\tt ba$,$S_3=\tt cdc$,$S_4=\tt aaba$,其中 $S_1$ 与 $S_3$ 为回文字符串。 **【数据范围】** 假定记号 $|S|$ 表示字符串 $S$ 的长度。 - 对于 $10\%$ 的数据,字符串至多包含一种字母; - 对于 $30\%$ 的数据,字符串至多包含两种字母; - 对于 $70\%$ 的数据,$|S|\leq 1000$; - 对于所有数据,$1 \leq |S| \leq 10^6$,字符串仅包含英语小写字母。