Counting Distinct Substrings

To count distinct substrings of a string, build a trie of all suffixes:

function countDistinctSubstrings(s):
    root = TrieNode()
    count = 0
    for i from 0 to s.length - 1:
        // Insert suffix starting at i
        node = root
        for j from i to s.length - 1:
            c = s[j]
            if c not in node.children:
                node.children[c] = TrieNode()
                count += 1  # new substring found
            node = node.children[c]
    return count

Each new node represents a unique substring. Time: $O(n^2)$. Space: $O(n^2)$ worst case.

For better efficiency, use suffix arrays with LCP, achieving $O(n \log n)$ time.