How Many Distinct Substrings

Difficulty: 2300 6000 ms 128 MB

strings suffix-array

Count the DISTINCT non-empty substrings of S.

Input: one line with the string S.

Output: the number of distinct substrings.

Constraints:

• 1 ≤ |S| ≤ 10⁵
• lowercase letters

Sample Tests

ababa

9

aaa

3

Read the Editorial