#P1117. [NOI2016] 优秀的拆分

    ID: 161 远端评测题 1500ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串2016NOI 系列O2优化枚举暴力后缀数组SA

[NOI2016] 优秀的拆分

题目描述

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

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

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

以下事项需要注意:

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

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 TT,表示数据的组数。

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

输出格式

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

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba
3
5
4
7

提示

样例解释

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

第一组数据中,共有三个子串存在优秀的拆分:
S[1,4]=aabbS[1,4]=\texttt{aabb},优秀的拆分为 A=a\text{A}=\texttt{a}B=b\text{B}=\texttt{b}
S[3,6]=bbbbS[3,6]=\texttt{bbbb},优秀的拆分为 A=b\text{A}=\texttt{b}B=b\text{B}=\texttt{b}
S[1,6]=aabbbbS[1,6]=\texttt{aabbbb},优秀的拆分为 A=a\text{A}=\texttt{a}B=bb\text{B}=\texttt{bb}
而剩下的子串不存在优秀的拆分,所以第一组数据的答案是 33

第二组数据中,有两类,总共四个子串存在优秀的拆分:
对于子串 S[1,4]=S[2,5]=S[3,6]=ccccS[1,4]=S[2,5]=S[3,6]=\texttt{cccc},它们优秀的拆分相同,均为 A=c\text{A}=\texttt{c}B=c\text{B}=\texttt{c},但由于这些子串位置不同,因此要计算三次;
对于子串 S[1,6]=ccccccS[1,6]=\texttt{cccccc},它优秀的拆分有两种:A=c\text{A}=\texttt{c}B=cc\text{B}=\texttt{cc}A=cc\text{A}=\texttt{cc}B=c\text{B}=\texttt{c},它们是相同子串的不同拆分,也都要计入答案。
所以第二组数据的答案是 3+2=53+2=5

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

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

数据范围

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

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

测试点编号 nn \leq 特殊性质
121 \sim 2 300300 SS 中所有字符相同
343 \sim 4 20002\,000
565 \sim 6 1010
787 \sim 8 2020
9109 \sim 10 3030
111211 \sim 12 5050
131413 \sim 14 100100
1515 200200
1616 300300
1717 500500
1818 10001\,000
1919 20002\,000
2020 3000030\,000