#P18348. Requiem for Qingyu

Requiem for Qingyu

Requiem for Qingyu

给定一个仅含小写英文字母的非空字符串 SS。

对于 SS 的一个非空子串 TT,如果存在一种把整个 SS 分成若干个非空连续段的方法,使得每一段都是 TT 的前缀,则称 TT 是好的。

形式化地,要求存在正整数 kk 和非空字符串 U(1),U(2),…,U(k)U^{(1)},U^{(2)},\ldots,U^{(k)},使得

S=U(1)U(2)⋯U(k),S=U^{(1)}U^{(2)}\cdots U^{(k)},

并且对于每个 1≤i≤k1\le i\le k,U(i)U^{(i)} 都是 TT 的前缀。各段的长度可以不同,也可以重复使用同一个前缀。

求满足条件的下标对 (l,r)(l,r) 的数量,其中 1≤l≤r≤∣S∣1\le l\le r\le |S|,且 T=SlSl+1⋯SrT=S_lS_{l+1}\cdots S_r 是好的。内容相同但出现位置不同的子串需要分别计数。

输入格式

第一行一个整数 tt,表示测试用例数。

接下来 tt 行,每行一个非空字符串 SS。

数据范围:

  • 1≤t≤1051\le t\le 10^5;
  • 1≤∣S∣≤1051\le |S|\le 10^5;
  • SS 仅含从 a 到 z 的小写英文字母;
  • 一个输入文件中所有字符串的长度之和不超过 2×1052\times10^5。

输出格式

对于每个测试用例,输出一行一个整数,表示好的子串出现次数。

样例输入 1

4
aaaa
abbaabba
abaababa
qingyuislittlecyanfish

样例输出 1

10
8
13
1

说明

例如,当 S=aabS=\texttt{aab} 时,子串 ab\texttt{ab} 是好的,因为可以取划分 a∣ab\texttt{a}\mid\texttt{ab}。因此,不能额外要求 TT 本身必须是 SS 的前缀。

当 S=aaaaS=\texttt{aaaa} 时,任意非空子串都是好的,共有 4⋅5/2=104\cdot5/2=10 个出现位置。