5649：对折的字符串

给出一个包含 $$n$$ 个数字的字符串 $$T$$ ,字符串 $$T$$ 被称为对折的字符串，当且仅当其满足以下几个条件：

$$1.T$$非空.

$$2.T$$ 包含偶数个数字.

$$3.T$$ 从 $$ 1 $$ 个数字 到 $$ \frac{n}2$$ 个数字都是相同的。

$$4.T$$ 从$$(\frac{n}2+1)$$个数字到 $$n$$ 个数字都是相同的.

$$5.T$$ 的第 $$1$$ 个字符的数字加 $$1$$，等于 $$T$$ 的第 $$n$$  个字符的数字。

例如，$$1122、01$$ 和 $$444555$$ 都是对折的字符串，但 $$1222$$ 和 $$99$$ 不是。

请找出 $$T$$ 的所有子串中，是对折的字符串的子串的个数。

注意：即使两个子串作为字符串内容相同，只要它们在 $$T$$ 中的起始位置或结束位置不同，就视为不同的子串分别计数。

输入包含一个字符串 $$T$$.

输出 $$T$$ 的非空子串中对折的字符串的个数.

【样例输入1】

1122

【样例输入2】

7788788

【样例输入3】

2025

【样例输入4】

1112222334445556555

【样例输出1】

2

【样例输出2】

3

【样例输出3】

0

【样例输出4】

11

对于所有测试数据有：$$ 1 \le n \le 10^6$$.

TKKACM训练赛 Round#1