4112: 「NOI2016」优秀的拆分
内存限制：512 MB
时间限制：1.500 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意**非空**字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $ \texttt{aabaabaa} $ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。
现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
3. 字符串本身也是它的一个子串。
输入
每个输入文件包含多组数据。
输入文件的第一行只有一个整数 $T$，表示数据的组数。
接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。
输出
输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。
样例输入 复制
4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba样例输出 复制
3
5
4
7提示
数据范围：对于全部的测试点，$1 \leq T \leq 10, \ n \leq 30000$。 各测试点具体限制如下： |测试点|$n\le$|特殊性质| |:-:|:-:|:-:| |$1,~2$|$300$|$S$ 中所有字符相同| |$3,~4$|$2000$|$S$ 中所有字符相同| |$5,~6$|$10$|无特殊限制| |$7,~8$|$20$|无特殊限制| |$9,~10$|$30$|无特殊限制| |$11,~12$|$50$|无特殊限制| |$13,~14$|$100$|无特殊限制| |$15$|$200$|无特殊限制| |$16$|$300$|无特殊限制| |$17$|$500$|无特殊限制| |$18$|$1000$|无特殊限制| |$19$|$2000$|无特殊限制| |$20$|$30000$|无特殊限制|