Coding interview: how do you implement a suffix automaton and explain clone states?

Question

Given a string s, build a suffix automaton (SAM) online. Implement extend(c), explain len, link, transitions, and endpos, and use the structure to count distinct substrings, count pattern occurrences, or find a longest common substring. Explain why the number of states is O(n) and when a clone is required.

What the interviewer is testing

• Whether you can describe a state as an endpos equivalence class rather than an ordinary trie node.
• Whether you distinguish the direct-link, root-link, and clone branches during construction.
• Whether you preserve len[link[v]] < len[v], deterministic transitions, and the suffix-link tree invariant.
• Whether you can turn the structural invariant into query and complexity results.

Model answer

A SAM is the minimal partial DFA recognizing every substring of the source string. State v stores the maximum represented length len[v]; link[v] points to the longest suffix in another equivalence class. The state represents the consecutive interval (len[link[v]], len[v]], so one state can stand for several substring lengths.

When a character is appended, create cur and walk suffix links, adding the missing transition. If an existing target q satisfies len[p]+1 == len[q], link cur directly to q. Otherwise copy q into a clone with len = len[p]+1, redirect the relevant transitions on the suffix-link path, and point both link[q] and link[cur] to the clone. The clone restores the consecutive-length invariant.

Every non-root state contributes len[v] - len[link[v]] distinct substrings. To count occurrences, initialize one for states corresponding to source prefixes, then propagate counts to suffix links in decreasing len order.

Implementation sketch

The pseudocode below shows the construction; transitions can use a hash map or an ordered map.

extend(c):
  cur = new state
  len[cur] = len[last] + 1
  p = last
  while p != -1 and c not in next[p]:
    next[p][c] = cur
    p = link[p]
  if p == -1:
    link[cur] = root
  else:
    q = next[p][c]
    if len[p] + 1 == len[q]:
      link[cur] = q
    else:
      clone = copy(q)
      len[clone] = len[p] + 1
      while p != -1 and next[p][c] == q:
        next[p][c] = clone
        p = link[p]
      link[q] = link[cur] = clone
  last = cur

Sum len[v] - len[link[v]] over non-root states for the distinct-substring count. For an occurrence count, follow transitions to the pattern state and read the count propagated in decreasing-length order.

Common pitfalls

• Treating the SAM as a trie that accepts only suffixes, instead of a compression of all endpos classes.
• Copying a clone's transitions but leaving its links inconsistent, which breaks later length intervals.
• Redirecting too few transitions because the suffix-link walk stops before the first state that no longer points to q.
• Counting every clone as a source-prefix occurrence, inflating all occurrence counts.
• Using a fixed transition array for a large alphabet without stating its memory and encoding assumptions.

Complexity trade-offs

With a fixed alphabet or hashed transitions, construction takes O(n) time and space, with at most about 2n-1 states. Ordered transition maps add a factor related to alphabet operations. SAM is a strong fit for many substring queries on one fixed text; suffix arrays can be easier to control for lexicographic traversal, LCP work, and cache locality.

The linear bound assumes online appends. Inserting or deleting in the middle, or updating both ends, needs a different structure; extend cannot simply be reused while preserving its invariant.

Start with the empty string, one character, repeated characters, and a clone-triggering input such as abbb. Then compare random strings against brute-force sets for distinct-substring and occurrence counts. For longest common substring, stream the second string through the SAM and follow suffix links on mismatches.

References

• CP-algorithms' SAM notes: state intervals, clone construction, and query formulas.
• Blumer et al.'s smallest-substring-automaton paper: the theoretical state and transition bounds.
• Carnegie Mellon string-algorithms notes: when suffix arrays and suffix automata are preferable.

Follow-up questions

Why does each state represent a consecutive length interval?

Substrings in one endpos class form a gap-free sequence of lengths. Suffix links identify the boundary class containing the longest proper suffix, so the interval is exactly (len[link[v]], len[v]].

When is a clone required?

If an existing target q has len[q] > len[p]+1, it is carrying two non-consecutive length ranges. Copying its transitions and splitting out a clone restores the invariant.

Why does the interval sum count distinct substrings?

State intervals are disjoint, and each represented length corresponds to one distinct substring. Summing each interval's size therefore counts every non-empty distinct substring once.

How should SAM and Aho–Corasick be compared?

SAM indexes all substrings of one text and supports aggregate statistics. Aho–Corasick indexes a known set of patterns for batch matching. Whether the text or the pattern set is fixed usually determines the better construction.

How do you find a longest common substring?

Build a SAM for S, then scan T. Follow transitions while tracking the current match length; on a mismatch, follow suffix links and retry. Keep the maximum length observed.