#2083. 「NOI2016」优秀的拆分
题目描述
如果一个字符串可以被拆分为 的形式，其中 和 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 aabaabaa ，如果令 A=aab，B=a，我们就找到了这个字符串拆分成 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 A=a，B=baa，也可以用 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。
现在给出一个长度为 的字符串 ，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
- 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
- 在一个拆分中，允许出现 。例如 cccc 存在拆分 A=B=c。
- 字符串本身也是它的一个子串。
输入格式
每个输入文件包含多组数据。
输入文件的第一行只有一个整数 ，表示数据的组数。
接下来 行，每行包含一个仅由英文小写字母构成的字符串 ，意义如题所述。
输出格式
输出 行，每行包含一个整数，表示字符串 所有子串的所有拆分中，总共有多少个是优秀的拆分。
样例
样例输入
4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba样例输出
3
5
4
7样例解释
我们用 表示字符串 第 个字符到第 个字符的子串（从 开始计数）。
第一组数据中，共有三个子串存在优秀的拆分：
S[1,4]=aabb，优秀的拆分为 A=a，B=b；
S[3,6]=bbbb，优秀的拆分为 A=b，B=b；
S[1,6]=aabbbb，优秀的拆分为 A=a，B=bb。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 。
第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 S[1,4]=S[2,5]=S[3,6]=cccc，它们优秀的拆分相同，均为 A=c，B=c，但由于这些子串位置不同，因此要计算三次；
对于子串 S[1,6]=cccccc，它优秀的拆分有两种：A=c，B=cc 和 A=cc，B=c，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 。
第三组数据中， 和 各有两种优秀的拆分，其中 是问题描述中的例子，所以答案是 。
第四组数据中，，，，， 各有一种优秀的拆分， 有两种优秀的拆分，所以答案是 。
数据范围与提示
对于全部的测试点，。
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 49 题。保留原作者与原赛事署名。