Suffix Automaton Clone States

End-Position Equivalence

For substring $x$ of $S$, $\operatorname{endpos}(x)$ is the set of positions where an occurrence of $x$ ends. Two substrings are equivalent when these sets are identical. A suffix-automaton state represents one equivalence class, not one individual substring.

State $v$ stores len[v], the maximum represented length. Its suffix link targets the class containing its longest proper suffix in a different class. The state represents exactly the lengths from $\operatorname{len}(\operatorname{link}(v))+1$ through $\operatorname{len}(v)$, contributing their difference to the number of distinct substrings.

Transitions append symbols and always increase maximum length, so the automaton is a DAG. For "abb", cloning separates "b" from "ab" because their end-position sets diverge.

State role	Represented substrings	Length interval	End positions in `"abb"`	Why they share a state
Root	Empty string	$0$	All boundaries by convention	Initial state
State for `"a"`	`"a"`	$[1,1]$	$\{0\}$	Only `"a"` ends at position $0$
Clone for `"b"`	`"b"`	$[1,1]$	$\{1,2\}$	Both `"b"` occurrences share these ends
Original state for `"ab"`	`"ab"`	$[2,2]$	$\{1\}$	`"ab"` ends only at position $1$
Final state	`"bb"`, `"abb"`	$[2,3]$	$\{2\}$	Both end exactly at position $2$

Online Extension without Cloning

Maintain last, the state for the complete processed text. Appending $c$ creates current with length len[last] + 1. Follow suffix links from last, adding every missing $c$ transition to current.

If traversal passes beyond the root, link current to the root. Otherwise it stops at $p$ with transition $p\xrightarrow{c}q$. When $\operatorname{len}(p)+1=\operatorname{len}(q)$, the transition is continuous and current.link = q; state $q$ already begins at the required minimum length, so no class split is needed.

The Clone Case

If traversal finds $p\xrightarrow{c}q$ but $\operatorname{len}(p)+1\lt\operatorname{len}(q)$, the transition is non-continuous. Create a clone with length len[p] + 1, copy $q$'s transitions and suffix link, and give it zero initial occurrences. Redirect suffix-chain $c$ transitions still targeting $q$ to the clone, then link both $q$ and current to it.

The clone preserves $q$'s transition language while splitting substring-length intervals and end-position classes. During decreasing-length occurrence propagation, descendant counts flow into the clone; cloning itself creates no new text ending.

State Trace

Why Clone?

Build the automaton for "abb". After "ab", the state for "ab" has maximum length $2$, and the root's b transition reaches that state.

Append the third b:

Create current with maximum length $3$ for the new prefix "abb".
Add a b transition from the previous last to current.
Follow the suffix link to the root, whose existing b transition reaches $q$, the former "ab" state.
The root has length $0$ and $q$ has length $2$, so $0+1\lt2$ and the transition is non-continuous.
Create a length-$1$ clone, copy $q$'s transitions and link, redirect the root's b transition to it, and link both $q$ and current to it.

The clone now represents "b" with ends $\{1,2\}$; $q$ represents "ab" with end $\{1\}$; and current represents "bb" and "abb" with end $\{2\}$.

Implementation and Applications

Each extension creates one ordinary state and at most one clone, giving at most $2n-1$ states for non-empty text. Propagate occurrence counts from longer states to suffix-link parents: ordinary prefix states start at one, clones at zero.

Membership follows transitions. A reached state's propagated count is the occurrence count. The number of distinct substrings is $\sum_{v\ne0}(\operatorname{len}(v)-\operatorname{len}(\operatorname{link}(v)))$. DAG path counts support lexicographic selection: paths[v] is the sum of 1 + paths[u] over outgoing transitions $v\to u$.

from dataclasses import dataclass, field
from functools import lru_cache


@dataclass
class State:
    length: int = 0
    link: int = -1
    transitions: dict[str, int] = field(default_factory=dict)
    occurrences: int = 0
    is_clone: bool = False


class SuffixAutomaton:
    def __init__(self, text: str = "") -> None:
        self.states = [State()]
        self.last = 0
        self._occurrences_propagated = False
        for symbol in text:
            self.extend(symbol)

    def extend(self, symbol: str) -> None:
        if self._occurrences_propagated:
            raise RuntimeError("cannot extend after occurrence propagation")

        current = len(self.states)
        self.states.append(State(
            length=self.states[self.last].length + 1,
            occurrences=1,
        ))
        p = self.last

        while p != -1 and symbol not in self.states[p].transitions:
            self.states[p].transitions[symbol] = current
            p = self.states[p].link

        if p == -1:
            self.states[current].link = 0
        else:
            q = self.states[p].transitions[symbol]
            if self.states[p].length + 1 == self.states[q].length:
                self.states[current].link = q
            else:
                clone = len(self.states)
                self.states.append(State(
                    length=self.states[p].length + 1,
                    link=self.states[q].link,
                    transitions=self.states[q].transitions.copy(),
                    occurrences=0,
                    is_clone=True,
                ))
                while p != -1 and self.states[p].transitions.get(symbol) == q:
                    self.states[p].transitions[symbol] = clone
                    p = self.states[p].link
                self.states[q].link = clone
                self.states[current].link = clone

        self.last = current

    def propagate_occurrences(self) -> None:
        if self._occurrences_propagated:
            return
        order = sorted(
            range(1, len(self.states)),
            key=lambda state: self.states[state].length,
            reverse=True,
        )
        for state in order:
            parent = self.states[state].link
            self.states[parent].occurrences += self.states[state].occurrences
        self._occurrences_propagated = True

    def state_for(self, substring: str) -> int | None:
        state = 0
        for symbol in substring:
            next_state = self.states[state].transitions.get(symbol)
            if next_state is None:
                return None
            state = next_state
        return state

    def contains(self, substring: str) -> bool:
        return self.state_for(substring) is not None

    def occurrence_count(self, substring: str) -> int:
        if substring == "":
            raise ValueError("empty occurrences need a boundary convention")
        self.propagate_occurrences()
        state = self.state_for(substring)
        return 0 if state is None else self.states[state].occurrences

    def distinct_substring_count(self) -> int:
        return sum(
            state.length - self.states[state.link].length
            for state in self.states[1:]
        )

    def kth_substring(self, k: int) -> str:
        @lru_cache(maxsize=None)
        def paths(state: int) -> int:
            return sum(
                1 + paths(destination)
                for destination in self.states[state].transitions.values()
            )

        total = paths(0)
        if not 1 <= k <= total:
            raise IndexError(f"k must lie in [1, {total}]")

        state = 0
        result: list[str] = []
        while True:
            for symbol, destination in sorted(self.states[state].transitions.items()):
                branch_size = 1 + paths(destination)
                if k > branch_size:
                    k -= branch_size
                    continue
                result.append(symbol)
                if k == 1:
                    return "".join(result)
                k -= 1
                state = destination
                break

    def clone_states(self) -> list[int]:
        return [i for i, state in enumerate(self.states) if state.is_clone]


def naive_distinct_substrings(text: str) -> list[str]:
    return sorted({
        text[left:right]
        for left in range(len(text))
        for right in range(left + 1, len(text) + 1)
    })


if __name__ == "__main__":
    traced = SuffixAutomaton("abb")
    assert len(traced.clone_states()) == 1
    clone = traced.clone_states()[0]
    assert traced.states[clone].length == 1
    assert traced.occurrence_count("b") == 2
    assert traced.occurrence_count("ab") == 1
    assert traced.occurrence_count("bb") == 1

    for text in ["", "a", "abb", "aaaa", "ababa", "banana", "mississippi"]:
        automaton = SuffixAutomaton(text)
        expected = naive_distinct_substrings(text)
        assert automaton.distinct_substring_count() == len(expected)
        assert all(automaton.contains(substring) for substring in expected)
        for index, substring in enumerate(expected, start=1):
            assert automaton.kth_substring(index) == substring
        print(text, len(automaton.states), automaton.clone_states(), len(expected))

Cookie Consent