J1 习题-10 魔法咒语的奥秘

题目描述

在魔法世界中,古老的咒语常常具有神秘的对称性。

一位年轻的魔法师发现了一串由大写字母组成的古老咒语 $S$。他注意到，从这串咒语中选择三个字母，按原有顺序组合后如果能形成回文结构，就可能迸发出强大的魔法力量。

请帮助这位魔法师找出这串咒语中所有可能蕴含魔力的三字母组合的数量。

一个三字母组合 $(i,j,k)$ 需满足:

• $1 \leq i < j < k \leq |S|$
• 由 $S_i$、$S_j$、$S_k$ 按顺序组成的字符串是回文串。

其中，$|S|$ 指的是 $S$ 的长度，$S_x$ 指的是 $S$ 中的第 $x$ 个字符。

输入格式

一行一串字符序列，仅由大写字母组成。

输出格式

一行一个整数，表示具有魔力的三字母组合的数量。

样例输入

ABCACC

样例输出

5

样例分析

以下五组字母组合都能形成回文串:

• $(1,2,4)$: A,B,A → ABA
• $(1,3,4)$: A,C,A → ACA
• $(3,4,5)$: C,A,C → CAC
• $(3,4,6)$: C,A,C → CAC
• $(3,5,6)$: C,C,C → CCC

提示：

• 回文串是指从前向后读和从后向前读都一样的字符串
• 注意字母的选取必须保持原有顺序

数据范围

对于 $100\%$ 的数据： $S$ 为长度从 $1$ 到 $2\ \times\ 10^5$ 的英文大写字母组成的字符串。