#P18348. Requiem for Qingyu
Requiem for Qingyu
Requiem for Qingyu
给定一个仅含小写英文字母的非空字符串 。
对于 的一个非空子串 ,如果存在一种把整个 分成若干个非空连续段的方法,使得每一段都是 的前缀,则称 是好的。
形式化地,要求存在正整数 和非空字符串 ,使得
并且对于每个 , 都是 的前缀。各段的长度可以不同,也可以重复使用同一个前缀。
求满足条件的下标对 的数量,其中 ,且 是好的。内容相同但出现位置不同的子串需要分别计数。
输入格式
第一行一个整数 ,表示测试用例数。
接下来 行,每行一个非空字符串 。
数据范围:
- ;
- ;
- 仅含从 a 到 z 的小写英文字母;
- 一个输入文件中所有字符串的长度之和不超过 。
输出格式
对于每个测试用例,输出一行一个整数,表示好的子串出现次数。
样例输入 1
4
aaaa
abbaabba
abaababa
qingyuislittlecyanfish
样例输出 1
10
8
13
1
说明
例如,当 时,子串 是好的,因为可以取划分 。因此,不能额外要求 本身必须是 的前缀。
当 时,任意非空子串都是好的,共有 个出现位置。