I - Number of Substrings
Editorial
/ 
/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
長さ N の文字列 S が与えられます。S の相異なる部分文字列の個数を求めてください。
制約
- 1 \leq N \leq 500,000
- S は英小文字からなる。
入力
S
出力
答えを一行に出力してください。
入力例 1
abcbcba
出力例 1
21
入力例 2
mississippi
出力例 2
53
入力例 3
ababacaca
出力例 3
33
入力例 4
aaaaa
出力例 4
5
Score : 100 points
Problem Statement
You are given a string of length N. Calculate the number of distinct substrings of S.
Constraints
- 1 \leq N \leq 500,000
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
abcbcba
Sample Output 1
21
Sample Input 2
mississippi
Sample Output 2
53
Sample Input 3
ababacaca
Sample Output 3
33
Sample Input 4
aaaaa
Sample Output 4
5