题目描述

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

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

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

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

以下事项需要注意：

出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。

在一个拆分中，允许出现$A=B$。例如$cccc$存在拆分$A=B=c$。

字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。输入文件的第一行只有一个整数$T$，表示数据的组数。保证$1 \le T \le 10$。

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

$1 \le n \le 30000$

输出格式

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

题目解析

同步赛考场上看到这题的部分分吓呆了。暴力95分这是什么意思？写发哈希，也不想去想正解了。

不过正解的思想还是不错的。

首先，我们发现只要找出所有形如$AA$的串即可。设有$A_i$个这样的串结束位置是$i$，有$B_i$个这样的串开始位置是$i$，则

$$ans = \sum_{i=1} ^ {n-1} {A_i B_{i+1}}$$

我们考虑怎样快速求出$A$和$B$。

我们枚举$AA$串中$A$的长度$L$。在原串上，我们每隔$L$设置一个关键点，可以发现，若$A$的长度为$L$，$AA$必定恰好经过某两个相邻的关键点。于是我们可以枚举$AA$经过的关键点。

考虑两个相邻的关键点$a,b$，有$b = a + L$，我们求出$a,b$的最长公共前缀$p$和最长公共后缀$s$。若$p + s \gt L$，$AA$串就一定存在，且可行的开始位置区间是$[a - s + 1, a + p - L]$，可行的结束位置区间是$[b - s + L, b + p - 1]$。由于每次是对一段区间加1，差分一波即可。

根据调和级数，枚举的时间复杂度

$$T(n) = \sum_{i=1} ^ {n} {O(\frac{n} {i})} = O(n \log n)$$

最长公共前后缀可用后缀数组实现。总时间复杂度$O(n \log n)$。