UOJ Logo Universal Online Judge

UOJ

#219. 【NOI2016】优秀的拆分

附件下载 统计

如果一个字符串可以被拆分为 AABB 的形式,其中 AB 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。

例如,对于字符串 aabaabaa,如果令 A=aabB=a,我们就找到了这个字符串拆分成 AABB 的一种方式。

一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=aB=baa,也可以用 AABB 表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。

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

以下事项需要注意:

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

输入格式

每个输入文件包含多组数据。输入文件的第一行只有一个整数 T,表示数据的组数。保证 1T10

接下来 T 行,每行包含一个仅由英文小写字母构成的字符串 S,意义如题所述。

输出格式

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

样例一

input

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

output

3
5
4
7

explanation

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

第一组数据中,共有 3 个子串存在优秀的拆分:

S[1,4]=aabb,优秀的拆分为 A=aB=b

S[3,6]=bbbb,优秀的拆分为 A=bB=b

S[1,6]=aabbbb,优秀的拆分为 A=aB=bb

而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 3

第二组数据中,有两类,总共 4 个子串存在优秀的拆分:

对于子串 S[1,4]=S[2,5]=S[3,6]=cccc,它们优秀的拆分相同,均为 A=cB=c,但由于这些子串位置不同,因此要计算 3 次;

对于子串 S[1,6]=cccccc,它优秀的拆分有 2 种:A=cB=ccA=ccB=c,它们是相同子串的不同拆分,也都要计入答案。

所以第二组数据的答案是 3+2=5

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

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

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

对于全部的测试点,保证 1T10。以下对数据的限制均是对于单组输入数据而言的,也就是说同一个测试点下的 T 组数据均满足限制条件。

我们假定 n 为字符串 S 的长度,每个测试点的详细数据范围见下表:

测试点编号 n 其他约束
1、2300S中所有字符全部相同
3、42000
5、610
7、820
9、1030
11、1250
13、14100
15200
16300
17500
181000
192000
2030000

时间限制:1.5s

空间限制:512MB

下载

样例数据下载