To count distinct substrings of a string, build a trie of all suffixes:
def countDistinctSubstrings(s):
root = TrieNode()
count = 0
for i in range(len(s)):
# Insert suffix starting at i
node = root
for j in range(i, len(s)):
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: . Space: worst case.
For better efficiency, use suffix arrays with LCP, achieving time.