# CF123D String

• 19通过
• 43提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 后缀数组,SA 排序 线段树
• 难度 NOI/NOI+/CTSC
• 时空限制 2000ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

给你一个字符串s。每一组数字l和r满足$1 <= l <= r <= |s|$，他们对应s的子字符串（从l至r并包括l,r）

现定义以一个形如F(string x, string y)的字符串函数。我们将要找到一个列表，其中字符串x的子串等于字符串y。我们根据配对的第一个数字的增加来对这组配对进行排序。函数$f（x，y）$的值等于列表中非空连续序列的数目。 例如：f(babbabbababbab,babb) = 6

• (1, 4)
• (4, 7)
• (9, 12) 它的连续序列为：
• (1, 4)(4, 7)
• (4, 7)(9, 12)
• (1, 4)(4, 7)(9, 12)

给定字符串s，求所有f(s, x)的和 （x为s的字串）

输入样例1解释：

• f(aaaa,a):

(1),(2),(3),(4)

(1)(2),(2)(3), (3)(4)

(1)(2)(3), (2)(3)(4)

(1)(2)(3)(4)

$f(aaaa,a)= 10$

以此类推， $f(aaaa,aa)=6$

$f(aaaa, aaa) = 3$

$f(aaaa, aaaa) = 1$

所以结果为10+6+3+1=20

## 题目描述

You are given a string $s$ . Each pair of numbers $l$ and $r$ that fulfill the condition $1<=l<=r<=|s|$ , correspond to a substring of the string $s$ , starting in the position $l$ and ending in the position $r$ (inclusive).

Let's define the function of two strings $F(x,y)$ like this. We'll find a list of such pairs of numbers for which the corresponding substrings of string $x$ are equal to string $y$ . Let's sort this list of pairs according to the pair's first number's increasing. The value of function $F(x,y)$ equals the number of non-empty continuous sequences in the list.

For example: $F(babbabbababbab,babb)=6$ . The list of pairs is as follows:

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

Its continuous sequences are:

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

Your task is to calculate for the given string $s$ the sum $F(s,x)$ for all $x$ , that $x$ belongs to the set of all substrings of a string $s$ .

## 输入输出格式

输入格式：

The only line contains the given string $s$ , consisting only of small Latin letters ( $1<=|s|<=10^{5}$ ).

输出格式：

Print the single number — the sought sum.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

## 输入输出样例

输入样例#1： 复制
aaaa

输出样例#1： 复制
20

输入样例#2： 复制
abcdef

输出样例#2： 复制
21

输入样例#3： 复制
abacabadabacaba

输出样例#3： 复制
188


## 说明

In the first sample the function values at $x$ equal to "a", "aa", "aaa" and "aaaa" equal 10, 6, 3 and 1 correspondingly.

In the second sample for any satisfying $x$ the function value is 1.

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。