Introduction

If you literally build a trie of all substrings, the naive construction is expensive because a length-n string has O(n^2) substrings. The first optimization insight is that you usually do not want a plain trie over all substrings at all. You want a data structure that shares repeated structure more aggressively, such as a suffix tree or suffix automaton.

Why the Naive Trie Blows Up

A direct approach inserts every substring:

1def all_substrings(s: str):
2    for i in range(len(s)):
3        for j in range(i + 1, len(s) + 1):
4            yield s[i:j]

That already produces O(n^2) strings. If you then insert each substring character by character into a trie, the worst-case construction cost can approach O(n^3) counting all copied work.

For short strings this is fine. For large strings it is the wrong abstraction.

Better Baseline: Insert Only Suffixes

Every substring is a prefix of some suffix. That means a trie of all suffixes already represents all substrings implicitly.

def all_suffixes(s: str):
    for i in range(len(s)):
        yield s[i:]

A suffix trie is still not optimal in memory, but it is much better than inserting every substring independently because shared prefixes are reused.

Stronger Optimization: Suffix Automaton

A suffix automaton stores all substrings in linear size relative to the input string and can be built in linear time. It is often a much better answer than "optimize the trie" because it attacks the right problem.

Here is a compact runnable suffix-automaton builder in Python:

1class State:
2    def __init__(self):
3        self.next = {}
4        self.link = -1
5        self.length = 0
6
7class SuffixAutomaton:
8    def __init__(self):
9        self.states = [State()]
10        self.last = 0
11
12    def extend(self, ch):
13        cur = len(self.states)
14        self.states.append(State())
15        self.states[cur].length = self.states[self.last].length + 1
16
17        p = self.last
18        while p >= 0 and ch not in self.states[p].next:
19            self.states[p].next[ch] = cur
20            p = self.states[p].link
21
22        if p == -1:
23            self.states[cur].link = 0
24        else:
25            q = self.states[p].next[ch]
26            if self.states[p].length + 1 == self.states[q].length:
27                self.states[cur].link = q
28            else:
29                clone = len(self.states)
30                self.states.append(State())
31                self.states[clone].next = self.states[q].next.copy()
32                self.states[clone].length = self.states[p].length + 1
33                self.states[clone].link = self.states[q].link
34
35                while p >= 0 and self.states[p].next.get(ch) == q:
36                    self.states[p].next[ch] = clone
37                    p = self.states[p].link
38
39                self.states[q].link = clone
40                self.states[cur].link = clone
41
42        self.last = cur
43
44    def contains(self, sub):
45        state = 0
46        for ch in sub:
47            if ch not in self.states[state].next:
48                return False
49            state = self.states[state].next[ch]
50        return True
51
52sam = SuffixAutomaton()
53for ch in "banana":
54    sam.extend(ch)
55
56print(sam.contains("nan"))   # True
57print(sam.contains("apple")) # False

This structure answers substring-existence queries efficiently and avoids the explosive growth of the naive all-substrings trie.

Compress Edges If You Really Need a Trie

If you must keep a trie-like structure, compress non-branching paths so edges store string segments instead of single characters. That converts the bloated suffix trie idea into something much closer to a suffix tree, which is the standard compressed form.

The key design principle is:

• do not store repeated single-character chains if one labeled edge can represent the same path

That saves both memory and traversal overhead.

Common Pitfalls

The biggest mistake is optimizing node representation while keeping the fundamentally wrong construction strategy. If you still insert every substring independently, you are fighting the symptom instead of the cause.

Another issue is forgetting the actual query workload. If you only need substring existence checks, suffix automata or suffix arrays may be more appropriate than any trie variant.

Developers also sometimes underestimate memory overhead from Python dictionaries or object-heavy node structures. On large inputs, implementation overhead can dominate the theoretical character count quickly.

Finally, do not confuse suffix trie, suffix tree, suffix automaton, and substring trie as if they were interchangeable. They solve related problems, but their size and performance characteristics differ dramatically.

Summary

• A naive trie over all substrings is usually too expensive because there are O(n^2) substrings.
• A suffix-based structure is a much better starting point because every substring is a prefix of some suffix.
• Suffix automata and suffix trees are the usual optimizations for large-scale substring indexing.
• If you must keep a trie, use compressed edges to avoid long single-child chains.
• The best optimization is often choosing the right substring index, not micro-optimizing the wrong one.