← 返回题目列表

Codeforces · 123/D

D. 字符串

中文机器翻译题面 查看原题

给你一个字符串 s。满足条件 1 ≤ l ≤ r ≤ |s| 的每对数字 l 和 r 对应于字符串 s 的一个子串,从位置 l 开始,到位置 r 结束(含)。

让我们像这样定义两个字符串 F(x, y) 的函数。我们将找到这样的数字对的列表,其中字符串 x 的相应子字符串等于字符串 y。让我们根据对的第一个数字的递增对这个对列表进行排序。函数 F(x, y) 的值等于列表中非空连续序列的数量。

例如:F(babbabbababbab, babb) = 6。配对列表如下:

(1, 4), (4, 7), (9, 12)

其连续序列为:

- (1, 4)
- (4, 7)
- (9, 12)
- (1, 4), (4, 7)
- (4, 7), (9, 12)
- (1, 4), (4, 7), (9, 12)

你的任务是计算给定字符串 s 的所有 x 的总和 F(s, x),即 x 属于字符串 s 的所有子字符串的集合。

输入

唯一一行包含给定的字符串 s,仅由小拉丁字母组成 (1 ≤ |s| ≤ 105)。

输出

打印单个数字 — 求和。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

aaaa

输出 #1

20

输入 #2

abcdef

输出 #2

21

输入 #3

abacabadabacaba

输出 #3

188

注意

在第一个样本中,x 处的函数值等于“a”、“aa”、“aaa”和“aaaa”,相应地等于 10、6、3 和 1。

在第二个样本中,对于任何满足 x 的函数值为 1。