#P5642. String

    ID: 4643 传统题 1000ms 256MiB 尝试: 52 已通过: 24 难度: 4 上传者: 标签>CF1600普及+/提高-KMPborder 链前缀出现次数统计

String

题目描述

给定一个字符串 S S ,假设其前缀子串 Stri=S[0..i] \text{Str}_i = S[0..i] ,字符串的长度为 N N 。例如,当 S="moreandmorecold" S = \text{"moreandmorecold"} 且 N=15 N = 15 时,有 Str0="m" \text{Str}_0 = \text{"m"} 、Str1="mo" \text{Str}_1 = \text{"mo"} 、Str2="mor" \text{Str}_2 = \text{"mor"} ,以此类推。

我们定义 c[i] c[i] 表示前缀子串 Stri \text{Str}_i 在字符串 S S 中出现的次数。现在,请你计算 c[0] c[0] 到 c[N−1] c[N-1] 的总和。

输入格式

第一行包含一个整数 T T ,表示测试用例的数量。
对于每个测试用例,仅有一行输入,包含一个仅由小写字母组成的字符串 S S ,字符串的长度小于 100000 100000 。

输出格式

对于每个测试用例,输出一个整数,表示 c[0]+c[1]+⋯+c[N−1] c[0] + c[1] + \dots + c[N-1] 的结果。

3
acacm
moreandmorecold
thisisthisththisisthisisthisththisis
7
19
82

提示

对于第一个测试用例:
在字符串 "acacm" 中,出现了两次 "a",两次 "ac",以及一次 "aca"、"acac" 和 "acacm"。因此答案为 2+2+1+1+1=7 2 + 2 + 1 + 1 + 1 = 7 。

相关

在下列比赛中:

kmp