软通动力-编程能力在线评测系统

Problem1049--#2083. 「NOI2016」优秀的拆分

1049: #2083. 「NOI2016」优秀的拆分

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

如果一个字符串可以被拆分为 $AABB\text{AABB}$ 的形式，其中 $A\text{A}$ 和 $B\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 $aabaabaa$ ，如果令 $A = aab$ ， $B = a$ ，我们就找到了这个字符串拆分成 $AABB\text{AABB}$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。
比如我们令 $A = a$ ， $B = baa$ ，也可以用 $AABB\text{AABB}$ 表示出上述字符串；但是，字符串 $abaabaa$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
在一个拆分中，允许出现 $A=B\text{A}=\text{B}$ 。例如 $cccc$ 存在拆分 $A = B = c$ 。
字符串本身也是它的一个子串。

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 $T$ ，表示数据的组数。
接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$ ，意义如题所述。

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

样例输入

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

样例输出

样例解释

我们用 $S [i, j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串（从 $1$ 开始计数）。

第一组数据中，共有三个子串存在优秀的拆分：
$S [1, 4] = aabb$ ，优秀的拆分为 $A = a$ ， $B = b$ ；
$S [3, 6] = bbbb$ ，优秀的拆分为 $A = b$ ， $B = b$ ；
$S [1, 6] = aabbbb$ ，优秀的拆分为 $A = a$ ， $B = bb$ 。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 $3$ 。

第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 $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$ ，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 $3 + 2 = 5$ 。

第三组数据中， $S [1, 8]$ 和 $S [4, 11]$ 各有两种优秀的拆分，其中 $S [1, 8]$ 是问题描述中的例子，所以答案是 $2 + 2 = 4$ 。

第四组数据中， $S [1, 4]$ ， $S [6, 11]$ ， $S [7, 12]$ ， $S [2, 11]$ ， $S [1, 8]$ 各有一种优秀的拆分， $S [3, 14]$ 有两种优秀的拆分，所以答案是 $5 + 2 = 7$ 。

对于全部的测试点， $\leq T \leq 10, \ n \leq 30000$ 。

Source/Category

[Submit] [Status]