300648: CF123D. String
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
String
题意翻译
给出字符串 $s$,定义子串 $a$ 在 $s$ 中的出现次数为 $cnt(a)$,求 $\sum \frac{cnt(a)(cnt(a)+1)}{2}$。题目描述
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