题目描述

给你一个字符串 $s$，要求计算所有长度为偶数的前缀在整个字符串中出现的总次数。

输入格式

输入仅一行，包含一个字符串 $s$。

字符串的长度满足 $|s| \leq 200000$。

输出格式

输出仅一行，一个整数，表示所有长度为偶数的前缀在整个字符串中出现的总次数。

abababc

6

样例解释

对于样例输入 abababc：

• 长度为 $2$ 的前缀是 ab，它在字符串中出现了 $3$ 次（起始位置分别为 $1, 3, 5$）。
• 长度为 $4$ 的前缀是 abab，它在字符串中出现了 $2$ 次（起始位置分别为 $1, 3$）。
• 长度为 $6$ 的前缀是 ababab，它在字符串中出现了 $1$ 次（起始位置为 $1$）。

因此，总次数为 $3 + 2 + 1 = 6$。