Home › String Algorithms › Suffix Automaton: Algorithm Analysis and Code

Suffix Automaton: Algorithm Analysis and Code

String Algorithms By Sarah Mitchell, Staff Software Architect 23 min read

1. Introduction and Core Concepts

A suffix automaton (SAM), also known as a DAWG (Directed Acyclic Word Graph), is one of the most powerful and elegant data structures in string algorithms. Formally, the suffix automaton of a string S is the minimal deterministic finite automaton (DFA) that recognizes the set of all substrings of S. Minimal means that among all DFAs accepting exactly the same language — the language of all substrings of S — the suffix automaton has the smallest possible number of states.

Why does this matter? A string of length n can have up to n * (n+1) / 2 distinct substrings, which is quadratic. Explicitly storing all substrings is infeasible for large inputs such as genomic sequences, log files, or document corpora. A suffix automaton compresses this entire set into a linear-sized automaton with at most 2n - 1 states and 3n - 4 transitions. This linear bound is what makes the suffix automaton so valuable: it gives you the expressive power of a suffix trie, which would require O(n^2) space, in O(n) space.

Unlike suffix arrays or suffix trees, which explicitly represent suffixes, the suffix automaton represents all substrings implicitly through paths in a directed acyclic graph. Every path starting from the initial state corresponds to a substring, and every substring corresponds to exactly one path. This property enables a wide range of operations — substring existence checks, counting distinct substrings, finding the longest common substring, counting occurrences of every substring, and finding the longest repeated substring — all in linear or near-linear time. For backend systems that handle pattern matching at scale, the suffix automaton is a foundational tool for building efficient search indexes, plagiarism detectors, and compression algorithms.

Core Definitions

To understand the suffix automaton, we need two key concepts: end positions and equivalence classes. For a string S, let endpos(sub) be the set of all positions in S where an occurrence of substring sub ends. For example, in S = "ababa", endpos("aba") = {3, 5} and endpos("ba") = {3, 5}. Two substrings are considered equivalent if they have the same endpos set. This equivalence relation partitions all substrings of S into at most 2n - 1 classes, and each class becomes a state in the automaton.

Each state v stores three essential attributes: len[v], the length of the longest string in its equivalence class; link[v], the suffix link pointing to the state representing the longest proper suffix that belongs to a different class; and next[v], the transition dictionary mapping characters to next states. The suffix link forms a tree rooted at the initial state, often called the link tree or parent tree, which is critical for counting occurrences and traversing the structure topologically.

Why Suffix Automaton Over Simpler Structures?

A naive approach to substring problems is to use a hash set of all substrings or a trie of all suffixes. Both explode in memory. A suffix automaton provides the same query capabilities with guaranteed linear construction time and memory. Its online construction algorithm — where characters are added one by one and the automaton remains valid after each extension — makes it ideal for streaming data, incremental indexing, and real-time text processing where the full string is not known in advance.

2. How It Works

The suffix automaton is built incrementally. Starting from an automaton that contains only the empty string (a single initial state), we extend it character by character. For each new character c appended to the current string, we create a new state cur representing the entire string seen so far. The invariant is that after processing prefix S[0..i], the automaton correctly represents all substrings of that prefix.

The core of the extension procedure lies in handling suffix links and cloning. When we add c, we first try to add a transition labeled c from all suffixes of the previous string that do not already have such a transition. We walk suffix links from the previous last state last until we find a state p that already has a transition on c or we fall off the automaton. This walk ensures that every new substring ending with c is represented.

If we fall off (no such p exists), we simply link cur to the initial state. Otherwise, let q = next[p][c]. If len[p] + 1 == len[q], then q is the correct suffix link for cur. If not, the equivalence class of q needs to be split. We clone q into a new state clone that copies its transitions and suffix link but has length len[p] + 1. We then redirect suffix links of both q and cur to clone, and fix transitions that previously pointed to q to point to clone where appropriate. This cloning step is what keeps the automaton minimal and linear.

The Suffix Link Tree

Suffix links are not just auxiliary pointers; they define a tree that encodes the occurrence relationships between substrings. The suffix link of a state v points to the state representing the longest proper suffix of the longest string of v that is in a different equivalence class. Consequently, all substrings corresponding to a state are suffixes of the substrings of its ancestors in the link tree. This tree is used to propagate occurrence counts: if a substring occurs k times, its suffix link ancestor occurs at least k times.

Transitions as a DAG

The transition graph of a suffix automaton is a DAG with a single source (the initial state). Every substring corresponds to a unique path from the source, and the automaton is deterministic: from any state, there is at most one transition per character. Because the automaton is acyclic when ignoring suffix links, we can perform dynamic programming over it in topological order sorted by len to compute quantities like the number of distinct substrings or the lexicographically k-th substring.

Invariants Maintained

Throughout construction, three invariants hold: First, the automaton accepts exactly the set of substrings of the processed prefix. Second, the number of states never exceeds 2n - 1. Third, for every state, len[link[v]] < len[v] and all strings in the class of v have lengths in the interval (len[link[v]] + 1 .. len[v]). These invariants allow us to reason about correctness and derive formulas such as the total number of distinct substrings being the sum over all states of len[v] - len[link[v]].

3. Implementation

Implementing a suffix automaton in Python requires careful handling of states, transitions, and cloning. While Python is not as fast as C++ for competitive programming, a clean dictionary-based implementation is perfectly suitable for strings up to several hundred thousand characters and is excellent for understanding the logic. For production use with millions of characters, you would replace dictionaries with arrays for a fixed alphabet.

The implementation below defines a State class and a SuffixAutomaton class with an online extend method. The build method simply iterates over the input string. Pay close attention to the cloning logic: the clone must copy transitions deeply, inherit the suffix link, and start with zero occurrence count to avoid double-counting.

class State:
    def __init__(self):
        self.next = {}      # transitions: char -> state index
        self.link = -1      # suffix link
        self.len = 0        # max length of strings in this class
        self.occ = 0        # number of end positions (occurrences)
        self.first_pos = -1 # optional: first occurrence position

class SuffixAutomaton:
    def __init__(self):
        self.states = [State()]  # state 0 is the initial state
        self.states[0].link = -1
        self.last = 0            # state representing whole string

    def extend(self, c):
        cur = len(self.states)
        self.states.append(State())
        self.states[cur].len = self.states[self.last].len + 1
        self.states[cur].occ = 1
        self.states[cur].first_pos = self.states[cur].len - 1

        p = self.last
        # add transition for all suffixes that lack it
        while p != -1 and c not in self.states[p].next:
            self.states[p].next[c] = cur
            p = self.states[p].link

        if p == -1:
            self.states[cur].link = 0
        else:
            q = self.states[p].next[c]
            if self.states[p].len + 1 == self.states[q].len:
                self.states[cur].link = q
            else:
                # clone state q
                clone = len(self.states)
                self.states.append(State())
                self.states[clone].len = self.states[p].len + 1
                self.states[clone].next = self.states[q].next.copy()
                self.states[clone].link = self.states[q].link
                self.states[clone].first_pos = self.states[q].first_pos
                # clone does not correspond to new end position
                self.states[clone].occ = 0

                while p != -1 and self.states[p].next.get(c) == q:
                    self.states[p].next[c] = clone
                    p = self.states[p].link

                self.states[q].link = clone
                self.states[cur].link = clone
        self.last = cur

    def build(self, s):
        for ch in s:
            self.extend(ch)
        return self

This construction is fully online. You can call extend as characters arrive from a stream, and after each call the automaton is valid. The time per extension is amortized O(1) for a constant alphabet, or O(log sigma) if transitions are stored in balanced trees. In Python, dictionary operations are expected O(1).

Once built, the automaton can answer many queries without rebuilding. The next code blocks demonstrate how to compute the number of distinct substrings and how to count occurrences of any pattern. Both rely on processing states in order of decreasing length, which is a topological order of the suffix link tree and the DAG.

def count_distinct_substrings(sam):
    # sum over states of len[v] - len[link[v]]
    total = 0
    for i in range(1, len(sam.states)):
        link = sam.states[i].link
        total += sam.states[i].len - sam.states[link].len
    return total

def prepare_occurrences(sam):
    # propagate occurrence counts from longer to shorter states
    order = sorted(range(len(sam.states)), key=lambda x: sam.states[x].len, reverse=True)
    for v in order:
        link = sam.states[v].link
        if link != -1:
            sam.states[link].occ += sam.states[v].occ

def count_occurrences(sam, pattern):
    # walk automaton with pattern; if missing, count is 0
    v = 0
    for ch in pattern:
        if ch not in sam.states[v].next:
            return 0
        v = sam.states[v].next[ch]
    return sam.states[v].occ

# Example usage
sam = SuffixAutomaton().build("ababa")
prepare_occurrences(sam)
print(count_distinct_substrings(sam))  # 9 distinct substrings
print(count_occurrences(sam, "aba"))   # 2 occurrences

For problems like longest common substring between two strings, we do not need to build a second automaton. We build a suffix automaton for the first string S and then traverse it with the second string T, maintaining the current matched length l and current state v. This yields an O(|S| + |T|) solution.

def longest_common_substring(sam, t):
    v = 0
    l = 0
    best = 0
    best_pos = 0
    for i, ch in enumerate(t):
        if ch in sam.states[v].next:
            v = sam.states[v].next[ch]
            l += 1
        else:
            while v != -1 and ch not in sam.states[v].next:
                v = sam.states[v].link
            if v == -1:
                v = 0
                l = 0
                continue
            else:
                l = sam.states[v].len + 1
                v = sam.states[v].next[ch]
        if l > best:
            best = l
            best_pos = i
    # extract substring from t
    start = best_pos - best + 1
    return t[start: best_pos + 1], best

sam = SuffixAutomaton().build("ababc")
print(longest_common_substring(sam, "babcab"))  # ('babc', 4)

A final utility is checking substring existence and enumerating substrings in lexicographic order. Because the automaton is deterministic and acyclic, a simple walk decides existence in O(|pattern|) time, and a DFS with DP can find the k-th lexicographically smallest distinct substring.

def contains(sam, pattern):
    v = 0
    for ch in pattern:
        if ch not in sam.states[v].next:
            return False
        v = sam.states[v].next[ch]
    return True

def count_substrings_dp(sam):
    # DP: dp[v] = number of distinct substrings starting from v
    n = len(sam.states)
    dp = [0] * n
    order = sorted(range(n), key=lambda x: sam.states[x].len, reverse=True)
    for v in order:
        for to in sam.states[v].next.values():
            dp[v] += 1 + dp[to]
    return dp

def kth_substring(sam, k):
    # return k-th lexicographic distinct substring (1-indexed)
    dp = count_substrings_dp(sam)
    if k > dp[0] or k <= 0:
        return None
    v = 0
    res = []
    while k > 0:
        for ch in sorted(sam.states[v].next.keys()):
            to = sam.states[v].next[ch]
            cnt = 1 + dp[to]
            if k <= cnt:
                res.append(ch)
                if k == 1:
                    return ''.join(res)
                k -= 1
                v = to
                break
            else:
                k -= cnt
    return ''.join(res)

sam = SuffixAutomaton().build("ababa")
print(contains(sam, "bab"))  # True
print(contains(sam, "baa"))  # False
print(kth_substring(sam, 3)) # e.g., 'aba'

4. Step-by-Step Example

Let us walk through building the suffix automaton for S = "ababa" step by step. This string is ideal because it contains repeated patterns and triggers cloning, illustrating all cases of the algorithm.

We start with state 0: len=0, link=-1. This is the initial state representing the empty string.

Step 1: extend 'a' — Create state 1 with len=1. From state 0, there is no transition on 'a', so we add next[0]['a']=1. Since p becomes -1, we set link[1]=0. Last = 1. The automaton now accepts substrings {"a"}.

Step 2: extend 'b' — Create state 2 with len=2. Walk from last=1: state 1 has no 'b', so add next[1]['b']=2, move to link[1]=0. State 0 also has no 'b', so add next[0]['b']=2, move to -1. Set link[2]=0. Last = 2. Substrings: {"a","b","ab"}.

Step 3: extend 'a' — Create state 3 with len=3. Walk from last=2: state 2 has no 'a', add next[2]['a']=3, move to link[2]=0. State 0 has next[0]['a']=1, so p=0, q=1. Check if len[p]+1 == len[q]: 0+1 == 1 is true, so we set link[3]=1 without cloning. Last = 3. This step shows the straightforward case where the existing transition already satisfies the length condition.

Step 4: extend 'b' — Create state 4 with len=4. Walk from last=3: state 3 has no 'b', add next[3]['b']=4, move to link[3]=1. State 1 has next[1]['b']=2, so p=1, q=2. Check len[1]+1 == len[2]: 1+1 == 2 is true, so link[4]=2. Last = 4. No clone again.

Step 5: extend 'a' — Create state 5 with len=5. Walk from last=4: state 4 has no 'a', add next[4]['a']=5, move to link[4]=2. State 2 has next[2]['a']=3, so p=2, q=3. Now len[2]+1 = 3 and len[3]=3, so equality holds and link[5]=3. Wait, this example did not clone either. To see cloning, consider S = "abbb" or "abbab". Let us instead illustrate cloning with S = "ababa" if we had inserted differently: actually "ababa" does not clone in the standard construction? Let us check a string that does: S = "abacaba" or "aaaa" does not clone, but "abbb" does. For clarity, suppose we are at S="abbb" after "abb", and we add 'b' again: the transition from state 1 on 'b' goes to state 2 with len 2, but len[1]+1 =2 so no clone. A classic cloning example is S = "ababa" extended with another 'b' to make "ababab": at that point cloning occurs. The key takeaway is that cloning splits a state q into q and clone to preserve the interval property of lengths.

After building "ababa", we have 6 states (n+1 = 6, which is minimal for this string). The number of distinct substrings is computed as sum(len[v] - len[link[v]]) = (1-0)+(2-0)+(3-1)+(4-2)+(5-3)=1+2+2+2+2=9, which matches enumeration: "a","b","ab","ba","aba","bab","abab","baba","ababa".

To count occurrences, we initialize occ to 1 for each terminal state (states 1..5) and 0 for clones (none here). Sorting states by len descending (5,4,3,2,1,0) and propagating occ to suffix links gives: state 5 contributes to 3, state 4 to 2, state 3 to 1, and so on. The final occ values tell us that "aba" (state 3) occurs twice, "ab" (state 2) occurs twice, and "a" (state 1) occurs three times.

5. Complexity Analysis

The suffix automaton is celebrated for its linear guarantees. Construction is linear in the length of the string, and most queries are linear in the length of the query pattern or the answer size. This makes it suitable for large-scale string processing where quadratic algorithms would be infeasible.

Construction time is O(n * alphabet) in the worst case if transitions are stored in arrays, or O(n log sigma) with balanced trees, or expected O(n) with hash maps as in Python dictionaries. The cloning step is amortized constant time because each state is cloned at most once and each transition is redirected at most once. The suffix link walk in extend appears to be O(n) per character in the worst case, but the amortized analysis shows that the variable p only moves along suffix links decreasing len[p], so total work over the entire construction is O(n).

Space usage is O(n * sigma) in the worst case for array-based transitions, but with hash maps it is O(n) states and O(n) transitions, specifically at most 2n - 1 states and 3n - 4 transitions for n >= 3. Each state stores a dictionary of outgoing edges, a suffix link, and length. For a binary alphabet this is very compact; for large alphabets like Unicode, dictionary storage is essential.

Query complexities are equally attractive. Checking whether a pattern P of length m is a substring takes O(m) time by simply walking the automaton. Counting occurrences after O(n) preprocessing also takes O(m). Finding the longest common substring of S (length n) and T (length m) takes O(n + m) after building the automaton for S.

Operation Best Case Average Case Worst Case Space
Construction (n = |S|) O(n) O(n) O(n) O(n)
Substring Existence (|P| = m) O(m) O(m) O(m) O(1) extra
Count Occurrences of P O(m) O(m) O(m) O(n) for occ array
Number of Distinct Substrings O(n) O(n) O(n) O(n)
Longest Common Substring (S,T) O(|S| + |T|) O(|S| + |T|) O(|S| + |T|) O(|S|)
Longest Repeated Substring O(n) O(n) O(n) O(n)
k-th Lexicographic Substring O(n + answer length) O(n + answer length) O(n * sigma) O(n)

It is important to note that the O(n) construction assumes an alphabet of constant size or hash map operations in O(1). If the alphabet is large and transitions are stored in sorted arrays, each transition lookup costs O(log sigma), making construction O(n log sigma). In practice, for ASCII or lowercase English letters, array-based transitions are faster and more cache-friendly, while for Unicode or large alphabets, hash maps are preferred.

Memory can be the limiting factor for very large strings (e.g., 10^7 characters). Each state overhead in Python is significant due to object overhead. For such cases, implement the automaton in a lower-level language or use arrays of integers and dictionaries implemented via Python lists of dicts with __slots__ to reduce overhead. Alternatively, consider a suffix array with LCP, which is more memory-efficient in Python when using libraries like array or numpy.

6. Variations and Optimizations

The classic suffix automaton can be adapted and optimized for various scenarios. One common optimization is alphabet compression. If the input string uses only a small subset of Unicode, map characters to integers 0..sigma-1 and store transitions in lists of size sigma or in arrays of dictionaries keyed by integers. This reduces hashing overhead and improves cache locality.

Another variation is the minimal suffix automaton for a set of strings (also called a DAWG for a dictionary). Instead of building an automaton for a single string, we build it for multiple strings by resetting last to the initial state before each new string and not adding a separator. This structure recognizes all substrings of any string in the set, useful for multi-pattern matching and building generalized substring indexes for databases.

The suffix automaton with end position tracking augments each state with the minimal and maximal end position, or the first occurrence. This allows us to not only count occurrences but also locate the first or all occurrences of a pattern. By storing first_pos during construction and propagating minima via the link tree, we can answer "where does pattern P first appear?" in O(|P|) time.

Compressed and Succinct Representations

For memory-constrained environments, succinct suffix automata use bit vectors and compressed transition storage. Transitions can be stored in a single global hash map keyed by (state, char) or in adjacency lists sorted by character. Some implementations use double-array tries for transitions, achieving very low memory at the cost of more complex construction.

Online and Sliding Window Variants

The standard automaton is online for appending characters, but not for deletions. A sliding window suffix automaton that supports removing the first character (for streaming windows) is much more complex and typically requires rebuilding or using a different structure like a suffix tree with Ukkonen's algorithm extended for sliding windows. However, for many web server log analysis tasks, an append-only automaton is sufficient.

Alternative: SAM with DP for Counting

Instead of propagating occurrence counts via suffix links, you can compute DP over the DAG to count distinct substrings, count total occurrences, or find the longest path. Topological order by len ensures DP correctness. This DP approach also enables finding the number of different substrings that appear at least k times, or the longest substring that appears at least k times — both useful for data mining and bioinformatics.

7. Real-World Applications

Suffix automata are not just theoretical curiosities; they power real systems where substring queries must be answered quickly over large, often static, texts.

In web servers and search engines, suffix automata are used to build substring indexes for autocomplete and query suggestion. When a user types a prefix, the system needs to find all indexed terms containing that substring, not just those starting with it. A suffix automaton built over the corpus of indexed documents allows O(m) substring checks per query, enabling fast in-memory filtering before more expensive ranking.

In databases, substring search is a common operation for LIKE '%pattern%' queries. While B-trees and inverted indexes handle prefix and token search well, they are inefficient for arbitrary substring search. A suffix automaton (or its persistent variant) can serve as an auxiliary index for columns that require frequent substring matching, such as product descriptions or log messages. Some columnar databases use SAM-like structures for dictionary compression, where repeated substrings are replaced by references.

In bioinformatics, DNA sequences are strings over alphabet {A, C, G, T} with lengths in the billions. Finding the longest common substring between two genomes, counting repeated substrings (which may indicate regulatory elements), and locating all occurrences of a gene pattern are all classic SAM applications. The linear construction and O(m) query time are critical when n is 3 billion (human genome).

In network intrusion detection, deep packet inspection requires matching many patterns (signatures) against streaming network traffic. While Aho-Corasick is the standard for multi-pattern matching, a suffix automaton built over the traffic stream can detect any substring that matches a known malicious payload, especially when patterns are not known in advance but are defined as "any substring that appears at least k times" — a potential indicator of a worm or DDoS signature.

In data compression, the Lempel-Ziv family and related algorithms rely on finding the longest previous occurrence of the current substring. A suffix automaton can be used to maintain a sliding dictionary and find the longest match in O(m) time per position, though suffix trees and suffix arrays are more common here due to simpler implementation for this specific task.

Use Case Operation Used Time with SAM Example System
Substring Existence Check Walk automaton with pattern O(|pattern|) Code search, plagiarism detection
Count Distinct Substrings Sum len[v] - len[link[v]] O(n) Complexity analysis, uniqueness metrics
Longest Common Substring Traverse SAM of S with T O(|S| + |T|) Genome alignment, document similarity
Find All Occurrences Propagate occ via link tree O(n + output) Log analysis, intrusion detection
Longest Repeated Substring Max len[v] where occ[v] > 1 O(n) Data compression, bioinformatics
Lexicographically k-th Substring DP over DAG + DFS O(n + |answer|) String ranking, combinatorial generation

Beyond these, suffix automata are used in natural language processing for building subword vocabularies (similar to Byte Pair Encoding), in version control systems for finding common substrings between file revisions, and in music information retrieval for finding repeated motifs in symbolic music representations.

8. Comparison with Alternatives

Choosing the right string data structure depends on the operations you need, memory constraints, and whether you need online construction. The suffix automaton is one of several related structures, each with trade-offs.

A suffix trie is the simplest: a trie containing all suffixes of S. It has O(n^2) nodes in the worst case (e.g., S = "aaaa...a" still has O(n^2) distinct substrings? Actually suffix trie for "aaaa" has O(n^2) nodes). It is easy to understand but impractical for large n.

A suffix tree compresses the suffix trie by merging non-branching paths, achieving O(n) nodes. It can be built in O(n) with Ukkonen's algorithm and supports similar queries to SAM, but with larger constant factors and more complex implementation. Suffix trees explicitly represent suffixes and are better for problems requiring suffix array order or LCP queries.

A suffix array is a sorted array of all suffixes, plus an LCP array. It is the most memory-efficient (O(n) integers) and cache-friendly, and with RMQ can answer longest common prefix queries in O(1). However, substring existence requires binary search O(m log n), and construction, while O(n log n) or O(n) with SA-IS, is not online.

Aho-Corasick is not a substring index for a single text but a multi-pattern matcher for a dictionary of patterns. It builds a trie of patterns with failure links, similar in spirit to SAM's suffix links but for a different problem.

Feature Suffix Automaton Suffix Trie Suffix Tree Suffix Array + LCP
Number of States / Nodes ≤ 2n - 1 O(n^2) ≤ 2n - 1 n (array)
Construction Time O(n) O(n^2) O(n) (Ukkonen) O(n log n) typical
Memory (constant alphabet) O(n) O(n^2) O(n) O(n) (smallest)
Online (append character) Yes, O(1) amortized No Yes (Ukkonen) No
Substring Existence (m = |P|) O(m) O(m) O(m) O(m log n)
Count Distinct Substrings O(n) O(n^2) O(n) O(n)
Longest Common Substring O(n + m) O(n * m) O(n + m) O(n + m)
Implementation Complexity Moderate Easy High Moderate
Cache Friendliness Medium Poor Poor Excellent

In practice, if you need an online structure and only care about substrings (not lexicographic order of suffixes), suffix automaton is often the best choice. If you need to answer many LCP queries, range minimum queries, or find the k-th suffix, suffix array is superior. If you need to match many patterns against a streaming text, Aho-Corasick is the tool. Many production systems actually combine structures: for example, building a suffix array for static text and a suffix automaton for dynamic query processing.

9. Common Mistakes and Best Practices

Implementing and using suffix automata correctly requires attention to subtle details. The most frequent mistake is mishandling the clone's occurrence count. A clone state does not correspond to a new end position, so its occ must be initialized to 0, not 1. If you set it to 1, you will overcount occurrences for all substrings that map to the clone or its descendants. Only the newly created cur state gets occ = 1.

Another common error is forgetting to copy transitions deeply. In Python, clone.next = q.next would make both states share the same dictionary object, so later modifications to one would corrupt the other. Always use .copy(). Similarly, when redirecting transitions in the while loop, the condition must be next[p][c] == q, not just c in next[p], otherwise you may incorrectly redirect transitions that already point to the clone or another state.

A third pitfall is incorrect topological order for DP and occurrence propagation. States must be processed in decreasing order of len, not by creation order or BFS order. Creation order is not guaranteed to be sorted by length because clones have lengths that interleave. The standard trick is to use counting sort by length (since len is in [0..n]) for O(n) sorting, or simply use Python's sorted with key len for O(n log n) which is fine for moderate n.

Performance pitfalls include using Python recursion for DFS over the automaton, which can hit recursion limits for large automata (up to 2n states). Always use iterative stacks or explicit sorting. Also, storing transitions as Python dicts for a small alphabet like 'a'-'z' is wasteful; consider using a list of size 26 with -1 for missing transitions, or an array of dicts with __slots__ to reduce per-state overhead.

Best Practices