Count Distinct Substrings
hardStrings II+40 XPTime limit 3s
How many different non-empty substrings does a string have? aba has 6 substrings in total (a, b, a, ab, ba, aba) but only 5 different ones, since a appears twice. aaa has only 3: a, aa, aaa.
Input: one line with a string of lowercase letters.
Output: the number of distinct non-empty substrings (it can exceed 2³¹ — use 64-bit integers).
Constraints: 1 ≤ length ≤ 10⁵. Putting all substrings into a set is about n²/2 strings — far too many.
Think about it: a suffix automaton (or a suffix array with LCP) handles this in about O(n). In a suffix automaton every state v stands for the substrings with lengths in (len(link(v)), len(v)], and every distinct substring belongs to exactly one state — so the answer is the sum of len(v) − len(link(v)) over all states except the start. (With a suffix array: n(n+1)/2 − sum of LCPs.)
Sample input 1
aba
Sample output 1
5
Sample input 2
aaa
Sample output 2
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).