Problem10317--CF EDU - Suffix Array - Step 5 - A. Number of Different Substrings

10317: CF EDU - Suffix Array - Step 5 - A. Number of Different Substrings

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

Count the number of different substrings of the given string $s$.

Input

Input contains single string $s$ of length $n\ (1≤n≤400,000)$. The string consists of lowercase English letters.

Output

Print the number of different substrings in the given string.

Sample 1 Input 

ababba

Sample 1 Output 

15

Sample 2 Input 

mmuc

Sample 2 Output 

9

Sample 3 Input 

xmnnnuu

Sample 3 Output 

24


nnnn


4

HINT

CF EDU.

Source/Category

 
Submit