Count Distinct Substrings — Suffix Trie / Rolling Hash

Problem

Count the number of distinct substrings of a string.

Approach 1 — Suffix Trie (O(n²) space)

Insert all suffixes into a trie. Count = number of nodes (each node = one unique prefix = one unique substring end).

Approach 2 — Set of Substrings (O(n²) time/space)

s = "abcabc"
return len({s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1)})

Approach 3 — Rolling Hash O(n log n)

Solutions

Python — Suffix Trie

def countDistinctSubstrings(s: str) -> int:
    root={}; count=0
    for i in range(len(s)):
        node=root
        for c in s[i:]:
            if c not in node: node[c]={}; count+=1
            node=node[c]
    return count+1  # +1 for empty string (optional)

Complexity

• Suffix Trie: O(n²) time and space
• Suffix Automaton: O(n) (advanced)