Suffix Automaton, in depth: endpos classes, the clone step, linear-size bounds, occurrence counts, k-th substring and a full abcbc trace

End positions, classes and suffix links

For a substring t of s, let endpos(t) be the set of positions where occurrences of t end, counting from 1. In abcbc, endpos("bc") = {3, 5} and endpos("c") = {3, 5} as well, while endpos("b") = {2, 4}. Two substrings are equivalent when their endpos sets are equal. Each equivalence class becomes one state of the automaton.

Three facts make the structure work. If u is a suffix of w, then endpos(w) is a subset of endpos(u): wherever w ends, u ends too. Two endpos sets are either nested or disjoint. And the strings in one class are suffixes of each other, with consecutive lengths. If the longest string in a class has length len(v), the class contains exactly the suffixes of that string whose lengths run from len(link(v)) + 1 up to len(v).

The suffix link link(v) points to the class of the longest suffix that falls in a different class, meaning one with a strictly larger endpos set. Because the sets nest, suffix links form a tree rooted at the start state, whose endpos is every position. A state therefore needs only three fields: len, link and a transition map next. The shortest string in a state never needs storing, because it is implied by len(link(v)) + 1.

Online construction

Construction appends one character c at a time and maintains last, the state of the whole current string. Every new character creates a state cur for the new longest string. Then the algorithm walks the suffix-link chain from last and adds a c-transition to cur from every state that lacks one. Where the walk stops decides the suffix link of cur:

class SuffixAutomaton:
    def __init__(self):
        self.len = [0]        # len[v]: length of the longest string in state v
        self.link = [-1]      # suffix link; the root has none
        self.next = [{}]      # transitions: char -> state
        self.cnt = [0]        # 1 for states that end a prefix, 0 for clones
        self.last = 0

    def _new(self, length, link, nxt, cnt):
        self.len.append(length); self.link.append(link)
        self.next.append(nxt);   self.cnt.append(cnt)
        return len(self.len) - 1

    def extend(self, ch):
        cur = self._new(self.len[self.last] + 1, -1, {}, 1)
        p = self.last
        while p != -1 and ch not in self.next[p]:
            self.next[p][ch] = cur
            p = self.link[p]
        if p == -1:                                  # case 1: c is new
            self.link[cur] = 0
        else:
            q = self.next[p][ch]
            if self.len[p] + 1 == self.len[q]:       # case 2: q is solid
                self.link[cur] = q
            else:                                    # case 3: split q
                clone = self._new(self.len[p] + 1, self.link[q], dict(self.next[q]), 0)
                while p != -1 and self.next[p].get(ch) == q:
                    self.next[p][ch] = clone
                    p = self.link[p]
                self.link[q] = clone
                self.link[cur] = clone
        self.last = cur

def build(s):
    sam = SuffixAutomaton()
    for ch in s:
        sam.extend(ch)
    return sam

In case 1 no proper suffix of the old string can be extended by c, so the new string's only proper-suffix class is the root. In case 2 the walk reaches a state p that already has a c-transition to q, and q's longest string is exactly longest(p) + c. Then q is the class of the longest suffix of the new string that occurred before, and cur links to it. Case 3 is the subtle one.

The clone step

In case 3, q's longest string is longer than longest(p) + c. The class q mixes two kinds of strings. The short ones, up to length len(p) + 1, are suffixes of the new string and have just gained the new end position. The long ones have not. Their endpos sets now differ, so q has to split. The clone takes the short strings: it gets len(p) + 1, a copy of q's transitions and q's old suffix link. The original q keeps the long strings and now links to the clone. The walk then redirects to the clone every c-transition along the suffix-link chain that pointed at q, because those paths spell the short strings.

A clone does not mark the end of a new prefix, which is why its cnt starts at 0. That detail is essential for occurrence counting, and forgetting it is the most common bug in contest code.

Worked example: building abcbc

Here is the build of abcbc, step by step. Adding a, b and c only meets case 1, so states 1, 2 and 3 all link to the root. Adding the second b creates state 4 with len 4. The walk gives state 3 a b-transition, then reaches the root, which already maps b to state 2. Since len(root) + 1 = 1 but len(2) = 2, case 3 applies. Clone 5 is created with len 1 for the string "b", whose endpos is now {2, 4}. State 2 keeps "ab". Adding the second c creates state 6 with len 5. The walk gives state 4 a c-transition, then reaches clone 5, whose c goes to state 3 with len 3 > 2. So state 3 splits too: clone 7 with len 2 takes "bc" and "c", and transitions from 5 and from the root are redirected to it.

Summing len(v) - len(link(v)) over the non-root states gives 1 + 1 + 1 + 3 + 1 + 3 + 2 = 12. That is exactly the number of distinct non-empty substrings of abcbc, and a brute-force set confirms it.

Why the automaton stays linear

States. Each character adds cur and at most one clone, and the first two characters can never create a clone, so for n of at least 2 there are at most 1 + n + (n - 2) = 2n - 1 states. Strings such as abbb reach it: 7 states for n = 4. Transitions. At most 3n - 4 for n of at least 3. The proof takes a spanning tree of the transition graph, which has fewer edges than states, then charges each non-tree edge to a distinct non-empty suffix of s.

Time. The first walk adds transitions, and their total is bounded by the transition count. The redirect walk and the case analysis are amortised by a potential argument on the depth of last in the suffix-link tree. The total is O(n) operations on transitions. With an array of size sigma per state that is O(n) time but O(n * sigma) memory. With a balanced map it is O(n log sigma). With a hash map it is expected O(n). The common phrase "amortised O(1) per character" is only true for a fixed alphabet. The cost of copying transitions when cloning is also bounded by sigma per clone.

Queries: membership, occurrences, k-th substring, LCS

Membership. Walk next from the root, one character of p at a time. If every transition exists, p is a substring. The cost is O(|p|), independent of n.

Occurrences. Each non-clone state starts with cnt = 1 because it ends a prefix. Process states in decreasing len and add each cnt to its suffix link's. Afterwards cnt[v] equals |endpos(v)|, the occurrence count of every string in v. Sort by counting sort on len to keep the pass linear. The root's count is meaningless and should be ignored.

k-th distinct substring. Count the paths that start at each state, including the empty path, by processing states in decreasing len. Every transition goes to a state with larger len, so that order is topological. Then descend from the root, choosing characters in sorted order and skipping whole subtrees whose counts are smaller than k:

def occurrence_counts(sam):
    order = sorted(range(len(sam.len)), key=lambda v: sam.len[v], reverse=True)
    cnt = sam.cnt[:]
    for v in order:
        if sam.link[v] > 0:            # skip the root as a target
            cnt[sam.link[v]] += cnt[v]
    return cnt                       # cnt[v] = occurrences of every string in v

def kth_distinct(sam, k):
    order = sorted(range(len(sam.len)), key=lambda v: sam.len[v], reverse=True)
    paths = [1] * len(sam.len)       # 1 counts the empty path ending at v
    for v in order:
        for u in sam.next[v].values():
            paths[v] += paths[u]
    if k > paths[0] - 1:
        return None
    out, v = [], 0
    while k > 0:
        for ch in sorted(sam.next[v]):
            u = sam.next[v][ch]
            if k <= paths[u]:
                out.append(ch); k -= 1; v = u
                break
            k -= paths[u]
    return "".join(out)

On abcbc, kth_distinct returns a, ab, abc, abcb, abcbc, b, bc for k = 1 to 7. For occurrence-weighted ranking, which counts repeated substrings once per occurrence, initialise paths[v] with the occurrence count of v (0 for the root) and subtract that count instead of 1 when you step into a state.

Longest common substring. Feed a second string t through the automaton of s. When a transition is missing, follow suffix links and shrink the current match length to the new state's len. The longest match seen is the answer, in O(|t|) time. Longest common substring compares this with the DP and suffix-array approaches. For many strings, build a generalized automaton, inserting each string from the root with the extra check that avoids empty duplicate states, rather than joining the strings with separators.

Failure modes

• Clones counted as occurrences. Giving clones cnt = 1 inflates every count. Clones start at 0.
• Propagating in the wrong order. Counts must flow from longer len to shorter. Iterating by state id is wrong because clones are created after the states that link to them.
• Recursion depth. A recursive DFS over transitions overflows on aaaa... inputs, whose automaton is a chain. Use the len order instead.
• Memory blow-up. A dictionary per state in Python costs hundreds of bytes. For n in the millions, use flat arrays (array or NumPy) with a fixed alphabet mapping, or switch to a suffix array.
• Naive generalized automata. Inserting several strings by resetting last to the root without the extra case can create unreachable or duplicate states, which silently corrupts counts.

Trade-offs against other string indexes

What to do next

1. Type in the construction code and check it against brute force on random strings over {a, b} up to length 30: distinct counts, 2n - 1 states and 3n - 4 transitions.
2. Trace abcbc by hand, and check your table of len, link and endpos against the one above.
3. Add occurrence counts and confirm that state 7 reports 2 for "bc".
4. Implement kth_distinct, then its occurrence-weighted variant, and compare both with sorted brute-force lists.
5. Solve longest common substring by streaming one string through the other's automaton, and time it against the suffix-array method on 10^5-character inputs.
6. Port the dictionaries to flat arrays and measure memory per state before you use the automaton on large inputs.