Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Suffix automata: index substrings as text arrives

Last updated: 7 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A suffix automaton compresses the substrings of an append-only text into states distinguished by their possible continuations. Each state records its longest accepted string, a suffix link, and transitions by character. An append extends the current last state; when an existing transition would skip a length boundary, a clone copies that transition map and redirects the affected suffix chain. Following transitions from the initial state answers whether a pattern occurs anywhere. The empty pattern is present. Distinct substrings are counted by summing each noninitial state's longest length minus its suffix-link state's longest length. This is a character index, not a store of match positions or occurrence counts.

Operational case

Append the characters of dispatch-dispatch as incident text. The index finds patch and patch-dis, rejects warehouse, and counts 117 distinct nonempty substrings. Each append keeps earlier substring membership valid. A pattern may cross the hyphen because the hyphen is an ordinary character here; if entries should be isolated, use a separator that cannot appear in an entry and define whether cross-entry patterns are allowed. A new incident character extends the index without rebuilding the previous states. Deleting or replacing text is outside this implementation's contract.

Working Python program

python
"""Append-only suffix automaton for substring membership and distinct counts."""

from dataclasses import dataclass, field


@dataclass
class TextState:
    longest: int = 0
    suffix_link: int = -1
    next_state: dict[str, int] = field(default_factory=dict)


class IncidentTextAutomaton:
    def __init__(self):
        self.states = [TextState()]
        self.last = 0
        self.characters = 0

    def append(self, character: str) -> None:
        if len(character) != 1:
            raise ValueError("append exactly one character")
        current = len(self.states)
        self.states.append(TextState(longest=self.states[self.last].longest + 1))
        predecessor = self.last
        while predecessor >= 0 and character not in self.states[predecessor].next_state:
            self.states[predecessor].next_state[character] = current
            predecessor = self.states[predecessor].suffix_link
        if predecessor < 0:
            self.states[current].suffix_link = 0
        else:
            candidate = self.states[predecessor].next_state[character]
            if self.states[predecessor].longest + 1 == self.states[candidate].longest:
                self.states[current].suffix_link = candidate
            else:
                clone = len(self.states)
                original = self.states[candidate]
                self.states.append(TextState(self.states[predecessor].longest + 1, original.suffix_link, original.next_state.copy()))
                while predecessor >= 0 and self.states[predecessor].next_state.get(character) == candidate:
                    self.states[predecessor].next_state[character] = clone
                    predecessor = self.states[predecessor].suffix_link
                self.states[candidate].suffix_link = clone
                self.states[current].suffix_link = clone
        self.last = current
        self.characters += 1

    def contains(self, pattern: str) -> bool:
        state = 0
        for character in pattern:
            state = self.states[state].next_state.get(character, -1)
            if state < 0:
                return False
        return True

    def distinct_substrings(self) -> int:
        return sum(state.longest - self.states[state.suffix_link].longest
                   for state in self.states[1:])


incident_text = IncidentTextAutomaton()
for character in "dispatch-dispatch":
    incident_text.append(character)
print(incident_text.contains("patch"))
print(incident_text.contains("patch-dis"))
print(incident_text.contains("warehouse"))
print(incident_text.distinct_substrings())

Output

Output
True
True
False
117

Time, space, and tradeoff

For N appended characters, a suffix automaton has O(N) states and transitions when alphabet size is bounded; each nonempty text has at most 2N minus 1 states. The classic construction is O(N) total time with constant-time transition access, giving amortized O(1) per append. Python dictionaries offer expected constant-time access for ordinary keys, not an adversarial worst-case promise. A contains query follows M characters in expected O(M) time. The shown distinct-substring method scans all states on every call, so it costs O(N) time and O(1) extra working space; cache and update the total if repeated constant-time counts matter. Clone dictionary copies also depend on outgoing degree. Stored states use O(N) space for a fixed alphabet.

Common Mistakes

  • Do not read a failed transition as a partial substring match.
  • Do not omit the clone when an existing transition crosses the required length boundary.
  • Do not claim this membership API reports positions or frequency.
  • Do not apply append-only state to text deletions without rebuilding or choosing another index.

Connected lessons

Apply the invariant in the depot forest and notes project, then check the operations quiz.

Palindromic trees: index distinct palindromes as text arrives adds a distinct structure contract to compare.

Compressed suffix trees: locate patterns across a frozen text adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details