Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.