On this page

Suffix Automaton

Why this exists

You are given one string , maybe a genome, a book or a log file, and then a stream of questions about its substrings (contiguous pieces of ):

  • Does needle occur in ?
  • How many times does it occur? Where does it first occur?
  • How many different substrings does have?
  • What is the longest substring that shares with another string ?
  • What is the 1,000,000-th substring of in dictionary order?
  • What is the shortest string that does not occur in ?

A string of length has substrings, counted with repetition. For that is about . You cannot list them. You need a structure that represents all of them implicitly and answers questions by walking it.

The obvious structure is a trie of all suffixes (every substring is a prefix of some suffix, so this trie contains every substring as a path). It is correct, and it is enormous: one node per distinct substring. For a random DNA string of length 1,000 that is 496,316 nodes. The suffix automaton of the same string has 1,622 states and 2,545 transitions, and it answers the same questions. (Both numbers come from running the code on this page.)

The suffix automaton is the smallest deterministic finite automaton (DFA) that accepts exactly the suffixes of . Make every state accepting and the same graph accepts every substring of . It has at most states and transitions, it can be built online (one character at a time, left to right) in time for a fixed alphabet, and it has a second structure hidden inside it, the suffix-link tree, that turns many counting questions into one pass over states.

It was introduced under the name DAWG (directed acyclic word graph) by Anselm Blumer, Janet Blumer, David Haussler, Andrzej Ehrenfeucht, M. T. Chen and Joel Seiferas in "The smallest automaton recognizing the subwords of a text", Theoretical Computer Science 40 (1985). Maxime Crochemore developed it independently ("Transducers and repetitions", Theoretical Computer Science 45, 1986) and used it to compute longest common substrings in linear time. Competitive programmers rediscovered it in the 2000s; the cp-algorithms article is the standard modern reference and this lesson follows its notation.

This lesson is the second of the module's three "index the text" lessons, after Suffix Arrays & LCP. It is the hardest to understand and among the easiest to code: the construction is about 25 lines. The plan: build intuition with endpos classes, look at the finished automaton of abcbc, then build it one character at a time and slow down at the one tricky step (the clone). Then prove it is correct and linear, and use it for eight classic problems.

Pattern triggers

If the problem says or has…Think of…
"number of distinct substrings" of one string, up to over states
"how many times does each pattern occur" with patterns given after the textSuffix automaton + occurrence counts
"longest substring that occurs at least twice / at least times"Max over states with
"longest common substring of two strings", Automaton of one, walk the other:
Longest common substring of many stringsAutomaton of the first, walk each other string, keep the per-state minimum
"-th lexicographically smallest substring" (distinct, or counted with repetition)Count paths in the automaton DAG, then walk
"shortest string over the alphabet that does not occur"DP over states: shortest path to a missing transition
"after each appended character, report the number of distinct substrings"Online construction: each step adds
Sum over distinct substrings of Group by state:
One pattern, many textsKMP or Z, not an index
Many patterns known first, one textAho–Corasick indexes the patterns instead
Need sorted suffixes or LCP between suffixesSuffix Arrays (or the automaton of the reversed string, which gives the suffix tree)

The meta-trigger: the text is fixed, and the questions are about the set of its substrings or how often they occur. If you would like to "insert every substring into a hash set" but is too much, the automaton is that hash set, compressed.

Intuition & first principles

The analogy: a phone tree that merges identical branches

Imagine a trie of all suffixes of abcbc. Walk it and you see the same subtrees again and again. The node for bc and the node for abc both have exactly one way to continue to a suffix: they can be followed by bc, or by nothing. Their futures are identical. A trie keeps them as separate nodes because it remembers how you got there. An automaton does not need to remember the past, only what can still happen. So we merge every pair of nodes that have the same future. What remains is the suffix automaton.

"Same future" needs a precise definition. That definition is endpos.

A tiny example to hold in your head

Take $s = $ abcbc (indices 0 to 4). Its 12 distinct substrings are a, ab, abc, abcb, abcbc, b, bc, bcb, bcbc, c, cb, cbc.

For a substring , let be the set of indices in where an occurrence of ends:

Substring Occurrences (start..end)endpos
a0..0{0}
ab0..1{1}
b1..1, 3..3{1, 3}
abc0..2{2}
bc, cends at 2 and at 4{2, 4}
abcb, bcb, cbends at 3{3}
abcbc, bcbc, cbcends at 4{4}

Now group substrings with equal endpos sets. We get 7 groups, plus one more for the empty string (it "ends" everywhere, endpos by convention). Those 8 groups are exactly the 8 states of the suffix automaton of abcbc.

Why is "same endpos" the same as "same future"? A continuation turns into a suffix of exactly when some occurrence of ends at position . So the set of valid futures of is determined by , and different endpos sets give different future sets. This is the Myhill–Nerode idea from automata theory: the minimal DFA for a language has one state per class of "strings with the same set of valid continuations". For the language "suffixes of ", those classes are the endpos classes.

Vocabulary

  • DFA (deterministic finite automaton) — a directed graph of states with one start state; each edge (a transition) is labelled with a character, and no state has two outgoing edges with the same character. Reading a string means following its characters from the start.
  • Root — the start state, state 0. It stands for the empty string.
  • endpos — the set of end indices of the occurrences of in .
  • Equivalence class / state — a maximal set of substrings with the same endpos.
  • len — the length of the longest string in state . We write for that string.
  • minlen — the length of the shortest string in .
  • Suffix link — the state of the longest suffix of that is not in . The root has no link (we store ).
  • Suffix-link tree — the tree formed by all suffix links, rooted at the root.
  • Terminal state — a state containing a suffix of the whole string .
  • cnt — , the number of occurrences of every string in .

Four facts about endpos (each one makes the automaton small)

These are the lemmas everything else rests on. Each has a one-line reason.

Fact 1. If two non-empty substrings and with have the same endpos, then is a suffix of . Take any end index in the shared set. Both and end at , so the last characters of are .

Fact 2. For , endpos sets are either nested or disjoint: if is a suffix of then (wherever ends, its suffix ends too); otherwise they are disjoint (if both ended at , would be a suffix of ).

Fact 3. A state is a run of suffixes of consecutive lengths. Take a state and its longest string . By Fact 1, all strings of are suffixes of . Shortening a suffix can only keep endpos the same or make it bigger (Fact 2). So as you shorten one character at a time, endpos stays equal for a while (those strings are in ), then grows, and never comes back. The strings of are therefore the suffixes of with lengths in one interval . Look at state 4 above: cb, bcb, abcb, lengths 2, 3, 4.

Fact 4. The suffix links form a tree, and endpos grows toward the root. Shorten just past and you land in a different state with a strictly bigger endpos. That state is . Its len is exactly , so

Every link goes to a state with a strictly shorter longest string, so following links always reaches the root: the links form a tree. And .

These four facts already hint at why the automaton is small. The states form a tree whose sets (endpos) are nested subsets of , and the children of a state have disjoint sets. A tree like that cannot have many more nodes than it has elements; we prove the exact bound, , below.

And Fact 4 gives the most-used formula in the lesson. State holds exactly strings. Every distinct substring lives in exactly one state. So

Mechanics

The finished automaton of abcbc

Here are all 8 states. The table and diagrams were produced by running the construction below and enumerating the strings that reach each state.

StateStrings in itlenlinkminlenendposcntstrings = len − len(link)
0(empty)0−10all——
1a101{0}11
2ab252{1}11
3abc373{2}11
4cb, bcb, abcb452{3}13
5b101{1, 3}21
6cbc, bcbc, abcbc573{4}13
7c, bc201{2, 4}22

Sum of the last column: , the number of distinct substrings. The automaton has 8 states () and 9 transitions ().

The transitions (the DFA). Reading any substring from state 0 follows a unique path; a string that is not a substring falls off. Terminal states (suffixes of abcbc: abcbc, bcbc, cbc, bc, c, and the empty string) are marked ✓.

flowchart LR
    s0(("0 ✓"))
    s0 -->|a| s1["1: a"]
    s1 -->|b| s2["2: ab"]
    s2 -->|c| s3["3: abc"]
    s3 -->|b| s4["4: abcb, bcb, cb"]
    s4 -->|c| s6["6: abcbc, bcbc, cbc ✓"]
    s0 -->|b| s5["5: b"]
    s5 -->|c| s7["7: bc, c ✓"]
    s0 -->|c| s7
    s7 -->|b| s4

Try it: bcb goes 0 →b→ 5 →c→ 7 →b→ 4. State 4, correct. ca goes 0 →c→ 7, and 7 has no a edge: ca is not a substring.

The suffix-link tree, with each state's endpos. Read it bottom-up: every link drops the shortest-but-longer strings and lands in a state whose endpos is a superset.

flowchart BT
    n1["1: a, endpos 0"] --> r(("0 root"))
    n5["5: b, endpos 1 and 3"] --> r
    n7["7: bc, c, endpos 2 and 4"] --> r
    n2["2: ab, endpos 1"] --> n5
    n4["4: abcb, bcb, cb, endpos 3"] --> n5
    n3["3: abc, endpos 2"] --> n7
    n6["6: abcbc, bcbc, cbc, endpos 4"] --> n7

Notice how the leaves' endpos sets partition the parent's set: state 5 has endpos {1, 3}; its children 2 and 4 have {1} and {3}. The prefixes of (a, ab, abc, abcb, abcbc) are the non-clone states 1, 2, 3, 4, 6, one per end index. The clones, 5 and 7, are the internal nodes created to hold strings that occur more than once. This is the whole idea behind counting occurrences: give every prefix state a 1 and add counts up the tree.

The suffix-link tree is a suffix tree

The suffix-link tree of the automaton of is exactly the (implicit) suffix tree of the reversed string (Blumer et al. 1985; also in cp-algorithms). For example, state 4 holds cb, bcb, abcb; reversed they are bc, bcb, bcba, which sit on one edge of the suffix tree of cbcba. This is why Suffix Trees can be built by building an automaton.

Online construction: the idea

We add the characters of one at a time. After processing the prefix we have the correct automaton of that prefix, and a variable last, the state of the whole prefix (the state with the largest len). Appending one character creates new substrings: exactly the suffixes of that never occurred before. All of them end at the new index and nowhere else.

What needs to change?

  1. A new state cur for the whole new prefix . Its endpos is . .
  2. New transitions. Every suffix of the old prefix such that never occurred before now needs an edge by to cur. The suffixes of the old prefix are exactly the strings in the states on last's suffix-link chain: last, link(last), …, root. So we walk that chain, and at every state with no -edge, we add .
  3. A suffix link for cur. The walk stops at the first state that already has a -edge, say to . That means some string of , extended by , occurred before, so must be the state of the longest such string: the string , of length .

Step 3 has three cases:

  • 2a. The walk fell off the root (). The character never appeared before. Only the empty string is a suffix in a different class. $\text{link}(\text{cur}) = $ root.
  • 2b. (a solid edge). The longest string of is exactly . is the state we want. .
  • 2c. (a non-solid edge). This is the tricky case, next section.
flowchart TD
    A["create cur, len(cur) = len(last) + 1"] --> B["p = last, walk suffix links, add p -c-> cur while p has no c-edge"]
    B --> C{"walked past the root?"}
    C -->|yes| D["link(cur) = root"]
    C -->|no| E{"q = next(p, c): len(p) + 1 == len(q)?"}
    E -->|"yes: solid"| F["link(cur) = q"]
    E -->|"no: split q"| G["clone = copy of q with len(p) + 1"]
    G --> H["redirect p -c-> q to p -c-> clone, walking links while it pointed to q"]
    H --> I["link(q) = link(cur) = clone"]
    D --> Z["last = cur"]
    F --> Z
    I --> Z

The clone step, slowly

State holds the suffixes of with lengths in . Before we added , all of them had the same endpos. Now, the shorter ones, those of length , are suffixes of the new prefix: they just gained a new end position, . The longer ones, of length , did not (if one of them were a suffix of , its -less part would be a longer suffix of the old prefix with a -edge, and the walk would have stopped earlier).

So must split into two states:

  • the clone, holding the short strings, lengths . Its endpos is the old endpos plus .
  • itself, keeping the long strings, lengths , with its old endpos.

What does each piece inherit?

Fieldclone after the splitwhy
lenunchangedthe clone's longest string is
outgoing transitionscopy of 'sunchangedthe short strings had the same futures as the long ones in the past; future characters have not arrived yet
suffix link's old linkthe clonethe clone's shortest string is 's old shortest string; the clone is now the longest proper suffix class of
incoming transitionsfrom and every state above on the chain whose -edge pointed to the restthose are exactly the states whose strings are the short strings

And $\text{link}(\text{cur}) = $ clone, because the clone's longest string is now the longest suffix of the new prefix that occurred before.

The redirect loop is the part people get wrong. Starting at , follow suffix links upward, and while the -edge of the current state points to , point it to the clone instead. Stop at the first state whose -edge points somewhere else (to a state with even shorter strings) or at the root's parent. The states on the chain above that point already point to shallower states, which are correct.

Why the clone is a copy, not an empty state

A common bug is creating the clone with no transitions. The clone's strings are suffixes of 's strings and had the same endpos until this moment, so every character that could follow a long string of could also follow the short ones. The clone needs all of 's outgoing edges. Copying a map costs at most per clone, and the copied edges are counted inside the bound, so it does not hurt the linear time.

Trace: building the automaton of abcbc

abcbc is the smallest interesting example: it triggers two clones, one of which redirects two edges. Every row below was printed by an instrumented copy of the construction (the same one the trace generator scripts/traces/suffix_automaton_build.py uses).

StepReadNew cur (len)Walk: edges addedStopped at CaseCloneRedirectedLinks setStates / transitions after
1a1 (1)0 →a→ 1past root2a——link(1) = 02 / 1
2b2 (2)1 →b→ 2, 0 →b→ 2past root2a——link(2) = 03 / 3
3c3 (3)2 →c→ 3, 0 →c→ 3past root2a——link(3) = 04 / 5
4b4 (4)3 →b→ 40 (has b → 2)2c: len(0) + 1 = 1 < len(2) = 25: len 1, edges {c → 3}, link 00 →b→ 5link(2) = 5, link(4) = 56 / 7
5c6 (5)4 →c→ 65 (has c → 3)2c: len(5) + 1 = 2 < len(3) = 37: len 2, edges {b → 4}, link 05 →c→ 7, 0 →c→ 7link(3) = 7, link(6) = 78 / 9

Read steps 4 and 5 with the endpos table in mind.

Step 4 (second b). Before it, state 2 held ab and b, both with endpos {1}. Now b also ends at 3, but ab does not. They must separate. The walk from last = 3 adds 3 →b→ 4 (so abcb, bcb, cb reach the new state) and stops at the root, which already has a b-edge to 2. The edge is not solid: len(0) + 1 = 1 but len(2) = 2, so state 2 contains a string longer than "root + b". Clone: state 5 takes the short string b (len 1), copies 2's edge c → 3, copies 2's link (the root). The root's b-edge is redirected to 5. Finally link(2) = 5 (ab drops its first letter and lands on b) and link(4) = 5 (the longest suffix of abcb that occurred before is b).

Step 5 (second c). Now state 3 holds abc, bc, c, all with endpos {2}. But bc and c now also end at 4. The walk from last = 4 adds 4 →c→ 6 and moves to link(4) = 5, which already has a c-edge to 3. Not solid: len(5) + 1 = 2 < 3. Clone 7 takes bc and c (len 2), copies 3's edge b → 4 and 3's link (root). The redirect walk starts at 5: its c-edge points to 3, redirect to 7. Move to link(5) = 0: its c-edge also points to 3, redirect to 7. Move to the root's link, −1: stop. Two edges redirected. Then link(3) = 7 and link(6) = 7.

Step through the same construction in the visualizer. States that do not exist yet are greyed; grey dashed edges are transitions or links that do not exist at that moment (including the ones that get redirected away).

Terminal states

The suffixes of are the strings in the states on last's suffix-link chain. For abcbc: last = 6 → 7 → 0, so the terminal states are 6, 7 and the root. If you need "is a suffix of ?", mark those states after building; you do not need them for substring questions.

The ladder: brute force → better → optimal

Problem: preprocess (length ) so we can answer "how many distinct substrings?", "how many occurrences of ?" and "longest common substring with ?".

Rung 1: generate every substring

Put all substrings into a hash set. Each substring costs to hash or copy, so time and up to characters of memory. For occurrences, scan with a naive matcher, per query. This is the oracle every implementation on this page was tested against.

Rung 2: rolling hashes

With polynomial hashing, each substring's hash is , so the distinct count is expected time and memory (or memory per length, total time). Longest common substring: binary search on the length , and for each compare hash sets of length- windows: expected. Fast and practical, probabilistic.

Rung 3: trie of all suffixes

Insert every suffix into a trie: nodes and time. Queries become walks, and occurrence counts are subtree leaf counts. Exact, but quadratic memory: 496,316 nodes for 1,000 random DNA characters.

Rung 4: suffix array + LCP

Sort the suffixes (Suffix Arrays) in , compute the LCP array (Kasai, ). Distinct substrings . Occurrences of : binary search, . LCS of two strings: suffix array of , .

Rung 5: suffix automaton

build (times the cost of a transition lookup), for the distinct count, for all occurrence counts, then per occurrence query and for the LCS walk.

RungMethodBuildDistinct substringsOccurrences of LCS with Memory
1All substrings in a set after build chars
2Rolling hashes expected expected to
3Suffix trie (node count) naive
4Suffix array + LCP
5Suffix automaton array or map

Why rung 5 wins: it shares both prefixes (like a trie) and suffixes (states with equal futures are merged), and it is built incrementally, so it also answers "after each new character" questions.

Correctness

We prove that the construction maintains the automaton of the current prefix. The full proof is in Blumer et al. (1985) and Crochemore, Hancart & Lecroq, Algorithms on Strings (2007, ch. 5); here is the sketch with the key invariant.

Invariant

After processing , for every endpos class of substrings of (plus the empty string) there is exactly one state , with:

  1. ,
  2. = the state of the longest suffix of that is not in ,
  3. for every character , a transition exists iff the strings of followed by are substrings, and then is the class of those strings (all strings of extended by lie in one class, since they share endpos shifted by one, restricted to positions followed by ),
  4. last is the class of the whole prefix.

Inductive step (appending at index )

Which classes change? Only strings that end at gain an end position. Those are suffixes of the new prefix . Its suffixes split into two kinds: the long ones that never occurred before (they form a brand-new class with endpos , the state cur), and the short ones that occurred before. Let be the longest suffix of that occurred before. Every shorter suffix also occurred before (it is a suffix of ). So the "old" suffixes are exactly the suffixes of .

The first loop adds exactly the right edges into cur. A state on the old chain of last holds suffixes of the old prefix. If has no -edge, no string of followed by had occurred, so each is new: it ends only at , it belongs to cur, and is the correct transition. The loop stops at the first whose strings have occurring before; then , because states are visited in decreasing len order.

cur's link. By definition it is the class of , whose length is .

  • If the walk fell off the root, there is no non-empty : link to the root.
  • If , then . Every string of is a suffix of , so all of them end at too: 's endpos gains uniformly, stays one class, nothing else changes.
  • Otherwise 's strings longer than are not suffixes of (if one were, its -less part would be a suffix of the old prefix longer than with a -edge, and the walk would have stopped earlier). The strings of length are suffixes of and gain . So splits exactly at length , and the clone's fields follow from the definitions (table in the previous section). The states whose -edge must move to the clone are those whose strings have length : that is and the states above it on the chain, as long as their -edge pointed to . Higher states point to a class of even shorter strings, which is unaffected.

No other class changes: any string not a suffix of keeps its endpos, so its class and edges are unchanged; the edges into the new classes are exactly those added or redirected above. ∎

Why it is the smallest DFA for the suffixes

Two strings must lead to different states of any DFA accepting the suffixes of if some continuation makes a suffix but not . That happens exactly when . So any such DFA needs at least as many states as there are endpos classes (plus a dead state if it is complete), and ours has exactly that many. This is the Myhill–Nerode theorem applied to the finite language of suffixes.

Subtle point: suffixes versus substrings

The suffix automaton is the minimal DFA for the suffixes. If you make every state accepting, it accepts all substrings, but it is not always the minimal DFA for that language. The minimal "factor automaton" can be a little smaller: for abb the suffix automaton has 5 states, while the minimal DFA accepting the substrings of abb has 4 (we checked by minimizing both). Crochemore and coauthors discuss this distinction; in practice everyone uses the suffix automaton because it carries the endpos information.

The size bounds

States: at most for (Blumer et al. 1985). Each step creates cur and at most one clone, so at most 2 states per character. The first two characters never clone (a clone needs a non-solid edge, which needs a state of len reached from a shorter one). So the count is at most . The string abbb…b reaches it: every b after the first two clones. The tree view gives the same picture: the suffix-link tree has prefix states plus the root plus clones, and each clone has at least two children from the moment it is created (the split state and cur), so there are fewer than clones.

Transitions: at most for (Blumer et al. 1985; the cp-algorithms proof). Split the transitions into two kinds:

  • Solid (part of a longest path from the root to some state, i.e. ): they form a spanning tree of the states, so there are at most (states − 1) of them.
  • Non-solid: for each non-solid edge , build the string "longest path to , then , then the longest path from to a terminal state". It is a suffix of , and different non-solid edges give different suffixes (the first non-solid edge on the string's path identifies it). The whole string is reached by solid edges only, so it is never used. Hence at most non-solid edges.

That gives . The extra comes from the fact that both bounds cannot be tight at once: when the states reach (string abb…b) the transition count is small. The extremal string for transitions is abb…bc, which reaches exactly . Our script checked both extremal families for : a + b×(n−1) gives exactly states, and a + b×(n−2) + c gives exactly transitions; random strings never exceeded either bound.

Intuition: the automaton is "a tree of states plus at most one shortcut per suffix".

Complexity

Time: amortized for a constant alphabet

The construction has three loops whose single iterations can be long. Each is bounded globally.

  1. Adding edges into cur (first loop): every iteration creates a transition, and transitions are never deleted (redirects only move them). Total iterations .
  2. Copying the clone's edges: the copied edges are transitions of the final automaton (clones are never deleted), so total copying is again , or if you copy dense arrays of size .
  3. The redirect loop: this needs a potential argument. Let be the depth of last in the suffix-link tree (number of states on its chain, including the root). The first loop walks states up the chain and the redirect loop walks more. The new chain of cur consists of cur, then (in case 2c) the clone, then the -successors of the states above where the redirect loop stopped; so its length is at most . Each character therefore raises by at most 3 and every loop iteration lowers it by 1. Since always, the total number of iterations of both loops is at most .

So the whole build takes transition lookups. We measured this: on 20,000 random strings up to length 30, the depth bound held every time and the two loops together never took more than about 2.7 iterations per character.

Cost of one transition lookup:

Transition storageLookupMemory for (up to states)Notes
Dense array int[26] per state B = 208 MBFastest; competitive programming with lowercase letters; clone = copy 26 ints
std::map / TreeMap per stateabout entries, tens of bytes eachAny alphabet; deterministic order (handy for -th substring)
Hash map per state expectedsimilar, more constant overheadAny alphabet; used in this page's Python/Java/TS code
Sorted edge list per stateabout 3 × 4-byte entries per charCompact; good for static automata

So the build is with arrays, with ordered maps, and expected with hash maps. For the dense array costs MB; at it is 208 MB, which already breaks a typical 256 MB judge limit once you add other arrays. That is the main practical reason to know the map version.

Space

states, each with len, link, (optionally) first-occurrence and count, plus transitions. Rule of thumb from the bounds: at most states and edges.

Queries

QueryTimeHow
Is a substring?walk from the root
Occurrences of after precomputationwalk, read
First occurrence of walk, read
Number of distinct substrings oncesum of
LCS with amortizedwalk with link fallbacks
-th substring precomputation, then path counts in the DAG

Applications, one at a time

All examples use the automaton of abcbc from above unless stated. Every number was printed by the code.

1. Substring check

Walk from the root. If a transition is missing, is not a substring. , independent of . bcb reaches state 4; ca falls off at state 7.

2. Number of distinct substrings

for abcbc, matching the brute-force list of 12. The code checks this formula against a brute-force set on 500 random strings in each language (and 4,000 more in our Python harness).

Online variant. When you append a character, the new substrings are the suffixes of the new prefix that never occurred before: lengths through , so exactly of them. So "distinct substrings of every prefix" costs nothing extra. For abcbc: step 1 adds , step 2 adds , step 3 adds , step 4 adds (link(4) = 5, len 1), step 5 adds (link(6) = 7, len 2). Running totals: 1, 3, 6, 9, 12.

A clone adds no substrings

It is tempting to also add the clone's . Do not: a clone only regroups strings that already existed (they moved out of ). Only cur brings new strings.

3. Occurrence counts (topological order by len)

. Each end index belongs to exactly one "prefix state" (the cur created at step ). By Fact 4, is the union of the endpos of its children in the suffix-link tree, plus 's own index if is a prefix state. So:

  1. Set for every non-clone state except the root, for clones.
  2. Visit states in decreasing order of len and add to .

Decreasing len is a valid order because a link always points to a strictly smaller len: every child is processed before its parent. A counting sort on len makes it .

For abcbc: the order is 6, 4, 3, 2, 7, 1, 5, 0. Initial counts are 1 for states 1, 2, 3, 4, 6 and 0 for clones 5, 7. State 6 adds 1 to 7; 4 adds 1 to 5; 3 adds 1 to 7; 2 adds 1 to 5. Result: (b occurs twice), (bc and c twice each), all others 1. To count occurrences of , walk to its state and read .

Do not count clones as occurrences

Initializing clones with 1 is the most common bug. A clone does not correspond to a new end position; it is created by splitting an existing state. If you set 1, every string that occurs twice will report three.

4. First occurrence

Store = the end index of the first occurrence of 's strings. For cur it is (the current index ). For a clone it is , because the clone's strings occurred wherever 's did, first at the same place. Existing states never change it (new occurrences are always later). The first occurrence of starts at . For cbc: state 6, first = 4, start = 4 − 3 + 1 = 2. For bc: state 7, first = 2, start = 1.

All occurrences: walk the subtree of in the suffix-link tree (precompute children lists); each non-clone state in the subtree contributes the occurrence ending at . That is after preprocessing.

5. Longest common substring of two strings in

Build the automaton of . Walk while keeping a state and a length : the longest suffix of that is a substring of is in state and has length . For each character of :

  1. While is not the root and has no -edge: and (we drop to the longest strings of the parent class, which are all still matched).
  2. If has a -edge: follow it and . Otherwise ( is the root with no -edge) .
  3. Record the maximum .

This is the "longest match ending here" scan, the same shape as KMP with suffix links playing the role of the failure function. Each character increases by at most 1 and every link step decreases it, so the walk is amortized.

Trace with $s = $ abcbc and $t = $ cbcab:

charlink movesstate aftermatched suffix of best
0c—71c1
1b—42cb2
2c—63cbc3
3a6 → 7 ( = 2), 7 → 0 ( = 0)11a3
4b—22ab3

Two details to notice. At the state is 7, whose len is 2, but : is the matched length, not . Only after a link move do we set . And at we fall all the way to the root before a can be read. The answer, 3, is cbc.

6. -th lexicographic substring (distinct)

The automaton is a DAG, and every distinct substring is exactly one path from the root. Let count the paths starting at (including the empty one). Compute it in decreasing len order, which is a reverse topological order of the DAG: a transition always has , so successors are processed first. Then walk from the root: at each state, try the outgoing characters in alphabetical order; if , take that edge and decrease by 1 (the string ending here); otherwise subtract and try the next character.

For abcbc, (12 substrings + the empty one). The sorted substrings are a, ab, abc, abcb, abcbc, b, bc, bcb, bcbc, c, cb, cbc. For : edge a leads to state 1 with ; , so . Edge b leads to state 5 with : take it, . From 5, edge c leads to 7 with : take it, . Answer bc, the 7th in the list. For the version counted with multiplicity, replace the 1 for "stop here" with (see CSES 2109 below).

This is DP on a DAG: count paths, then reconstruct the -th one.

7. Shortest non-occurring string

Over an alphabet , find the shortest string that is not a substring of (lexicographically smallest among the shortest). Let be the length of the shortest string such that reading from falls off the automaton:

Compute in decreasing len order; reconstruct by taking the smallest achieving the minimum. For abcbc over the answer is aa (the root reads a to state 1, which has no a-edge). This is the "minimum excluded string" and appears as CSES-style and Codeforces problems; our harness checked it against brute force on 4,000 random strings.

8. Longest repeated substring, and other "group by state" sums

Any question of the form "over all distinct substrings , combine " where depends only on the number of occurrences becomes a sum over states, because all strings in a state share :

  • Longest substring occurring at least times: .
  • (Codeforces 802I): .
  • Number of distinct substrings of each length: each state covers lengths ; add 1 on that range with a difference array.

Implementation

The four snippets below build the automaton with a map per state, compute occurrence counts by counting sort on len, and expose: contains, count, firstOccurrence, distinctSubstrings and longestCommonSubstring. Each main asserts the abcbc numbers from this page (lens [0, 1, 2, 3, 4, 1, 5, 2], links [-1, 0, 5, 7, 5, 0, 7, 0], 12 distinct substrings, counts, first occurrences, the LCS of xabcbcy and zzbcbczz, which is bcbc at index 2 of ), then runs a stress test: 500 random strings over {a, b, c} of length 1 to 12, each checked against brute force for the distinct count, the state bound, contains/count/firstOccurrence on every substring plus three probes, and the LCS length (and that the reported LCS really occurs in both strings).

import random


class SuffixAutomaton:
    def __init__(self, s):
        self.next = [{}]      # next[v][c] = state reached from v by character c
        self.len = [0]        # len[v] = length of the longest string in state v
        self.link = [-1]      # link[v] = suffix link (the root has none)
        self.first = [-1]     # first[v] = end index of the first occurrence of v's strings
        self.is_clone = [False]
        self.last = 0         # the state of the whole string read so far
        for c in s:
            self._extend(c)
        self._count_occurrences()

    def _new_state(self, length, link, first, nxt, clone):
        self.next.append(nxt)
        self.len.append(length)
        self.link.append(link)
        self.first.append(first)
        self.is_clone.append(clone)
        return len(self.len) - 1

    def _extend(self, c):
        cur = self._new_state(self.len[self.last] + 1, -1, self.len[self.last], {}, False)
        p = self.last
        while p != -1 and c not in self.next[p]:   # 1. give every suffix without a c-edge one, to cur
            self.next[p][c] = cur
            p = self.link[p]
        if p == -1:                                  # 2a. c is a brand-new character
            self.link[cur] = 0
        else:
            q = self.next[p][c]
            if self.len[p] + 1 == self.len[q]:       # 2b. solid edge: q is exactly "p + c"
                self.link[cur] = q
            else:                                    # 2c. q is too long: split it with a clone
                clone = self._new_state(self.len[p] + 1, self.link[q], self.first[q],
                                        dict(self.next[q]), True)
                while p != -1 and self.next[p].get(c) == q:
                    self.next[p][c] = clone
                    p = self.link[p]
                self.link[q] = clone
                self.link[cur] = clone
        self.last = cur

    def _count_occurrences(self):
        """cnt[v] = |endpos(v)| = number of occurrences of any string of state v."""
        n = len(self.len)
        self.cnt = [0 if v == 0 or self.is_clone[v] else 1 for v in range(n)]
        buckets = [0] * (self.len[self.last] + 1)   # counting sort of states by len
        for v in range(n):
            buckets[self.len[v]] += 1
        for i in range(1, len(buckets)):
            buckets[i] += buckets[i - 1]
        order = [0] * n
        for v in range(n - 1, -1, -1):
            buckets[self.len[v]] -= 1
            order[buckets[self.len[v]]] = v
        for v in reversed(order):                    # longest first: children before parents
            if self.link[v] > 0:
                self.cnt[self.link[v]] += self.cnt[v]

    def _walk(self, p):
        v = 0
        for c in p:
            v = self.next[v].get(c, -1)
            if v == -1:
                return -1
        return v

    def contains(self, p):
        return self._walk(p) != -1

    def count(self, p):
        """Number of (possibly overlapping) occurrences of p; the empty string is not counted."""
        v = self._walk(p)
        return self.cnt[v] if v > 0 else 0

    def first_occurrence(self, p):
        v = self._walk(p)
        if v == -1:
            return -1
        return 0 if v == 0 else self.first[v] - len(p) + 1

    def distinct_substrings(self):
        return sum(self.len[v] - self.len[self.link[v]] for v in range(1, len(self.len)))

    def longest_common_substring(self, t):
        """(length, start index in t) of a longest common substring of s and t."""
        v = length = best = 0
        best_end = -1
        for i, c in enumerate(t):
            while v != 0 and c not in self.next[v]:   # shorten the match: drop to the suffix link
                v = self.link[v]
                length = self.len[v]
            if c in self.next[v]:
                v = self.next[v][c]
                length += 1
            if length > best:
                best, best_end = length, i
        return best, best_end - best + 1


def brute_count(s, p):
    return sum(1 for i in range(len(s) - len(p) + 1) if s[i:i + len(p)] == p)


def brute_lcs(s, t):
    best = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            if j - i > best and s[i:j] in t:
                best = j - i
    return best


if __name__ == "__main__":
    sam = SuffixAutomaton("abcbc")
    assert len(sam.len) == 8 and sum(len(m) for m in sam.next) == 9
    assert sam.len == [0, 1, 2, 3, 4, 1, 5, 2]
    assert sam.link == [-1, 0, 5, 7, 5, 0, 7, 0]
    assert sam.distinct_substrings() == 12
    assert [sam.count(p) for p in ["b", "bc", "cb", "abcbc", "ca"]] == [2, 2, 1, 1, 0]
    assert sam.first_occurrence("bc") == 1 and sam.first_occurrence("cbc") == 2
    assert SuffixAutomaton("xabcbcy").longest_common_substring("zzbcbczz") == (4, 2)

    rng = random.Random(7)
    for _ in range(500):
        s = "".join(rng.choice("abc") for _ in range(rng.randint(1, 12)))
        t = "".join(rng.choice("abc") for _ in range(rng.randint(0, 12)))
        sam = SuffixAutomaton(s)
        subs = {s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)}
        assert sam.distinct_substrings() == len(subs)
        assert len(sam.len) <= max(2, 2 * len(s) - 1)
        for p in list(subs) + ["ca", "aaa", "cbcb"]:
            assert sam.contains(p) == (p in subs)
            assert sam.count(p) == brute_count(s, p)
            assert sam.first_occurrence(p) == s.find(p)
        best, start = sam.longest_common_substring(t)
        assert best == brute_lcs(s, t) and t[start:start + best] in s
    print("suffix automaton OK")
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class SuffixAutomaton {
    final List<Map<Character, Integer>> next = new ArrayList<>();
    final List<Integer> len = new ArrayList<>();
    final List<Integer> link = new ArrayList<>();
    final List<Integer> first = new ArrayList<>();   // end index of the first occurrence
    final List<Boolean> isClone = new ArrayList<>();
    int[] cnt;                                       // cnt[v] = |endpos(v)|
    int last = 0;

    SuffixAutomaton(String s) {
        newState(0, -1, -1, new HashMap<>(), false);
        for (char c : s.toCharArray()) extend(c);
        countOccurrences();
    }

    private int newState(int length, int lnk, int fst, Map<Character, Integer> nxt, boolean clone) {
        next.add(nxt);
        len.add(length);
        link.add(lnk);
        first.add(fst);
        isClone.add(clone);
        return len.size() - 1;
    }

    private void extend(char c) {
        int cur = newState(len.get(last) + 1, -1, len.get(last), new HashMap<>(), false);
        int p = last;
        while (p != -1 && !next.get(p).containsKey(c)) {   // 1. add the missing c-edges
            next.get(p).put(c, cur);
            p = link.get(p);
        }
        if (p == -1) {
            link.set(cur, 0);                              // 2a. brand-new character
        } else {
            int q = next.get(p).get(c);
            if (len.get(p) + 1 == len.get(q)) {
                link.set(cur, q);                          // 2b. solid edge
            } else {                                       // 2c. split q with a clone
                int clone = newState(len.get(p) + 1, link.get(q), first.get(q),
                                     new HashMap<>(next.get(q)), true);
                while (p != -1 && Integer.valueOf(q).equals(next.get(p).get(c))) {
                    next.get(p).put(c, clone);
                    p = link.get(p);
                }
                link.set(q, clone);
                link.set(cur, clone);
            }
        }
        last = cur;
    }

    private void countOccurrences() {
        int n = len.size(), maxLen = len.get(last);
        cnt = new int[n];
        for (int v = 1; v < n; v++) cnt[v] = isClone.get(v) ? 0 : 1;
        int[] bucket = new int[maxLen + 2];                // counting sort by len
        for (int v = 0; v < n; v++) bucket[len.get(v) + 1]++;
        for (int i = 1; i <= maxLen + 1; i++) bucket[i] += bucket[i - 1];
        int[] order = new int[n];
        for (int v = 0; v < n; v++) order[bucket[len.get(v)]++] = v;
        for (int i = n - 1; i >= 0; i--) {                 // longest first
            int v = order[i];
            if (link.get(v) > 0) cnt[link.get(v)] += cnt[v];
        }
    }

    private int walk(String p) {
        int v = 0;
        for (char c : p.toCharArray()) {
            Integer u = next.get(v).get(c);
            if (u == null) return -1;
            v = u;
        }
        return v;
    }

    boolean contains(String p) { return walk(p) != -1; }

    int count(String p) {
        int v = walk(p);
        return v > 0 ? cnt[v] : 0;
    }

    int firstOccurrence(String p) {
        int v = walk(p);
        if (v == -1) return -1;
        return v == 0 ? 0 : first.get(v) - p.length() + 1;
    }

    long distinctSubstrings() {
        long total = 0;
        for (int v = 1; v < len.size(); v++) total += len.get(v) - len.get(link.get(v));
        return total;
    }

    /** {length, start index in t} of a longest common substring of s and t. */
    int[] longestCommonSubstring(String t) {
        int v = 0, length = 0, best = 0, bestEnd = -1;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            while (v != 0 && !next.get(v).containsKey(c)) {
                v = link.get(v);
                length = len.get(v);
            }
            Integer u = next.get(v).get(c);
            if (u != null) {
                v = u;
                length++;
            }
            if (length > best) {
                best = length;
                bestEnd = i;
            }
        }
        return new int[] {best, bestEnd - best + 1};
    }

    static int bruteCount(String s, String p) {
        int k = 0;
        for (int i = 0; i + p.length() <= s.length(); i++) if (s.startsWith(p, i)) k++;
        return k;
    }

    static int bruteLcs(String s, String t) {
        int best = 0;
        for (int i = 0; i < s.length(); i++)
            for (int j = i + 1; j <= s.length(); j++)
                if (j - i > best && t.contains(s.substring(i, j))) best = j - i;
        return best;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    static String randomString(Random rng, int lo, int hi) {
        StringBuilder sb = new StringBuilder();
        int n = lo + rng.nextInt(hi - lo + 1);
        for (int i = 0; i < n; i++) sb.append((char) ('a' + rng.nextInt(3)));
        return sb.toString();
    }

    public static void main(String[] args) {
        SuffixAutomaton sam = new SuffixAutomaton("abcbc");
        int transitions = 0;
        for (Map<Character, Integer> m : sam.next) transitions += m.size();
        check(sam.len.size() == 8 && transitions == 9, "sizes");
        check(sam.len.equals(List.of(0, 1, 2, 3, 4, 1, 5, 2)), "len");
        check(sam.link.equals(List.of(-1, 0, 5, 7, 5, 0, 7, 0)), "link");
        check(sam.distinctSubstrings() == 12, "distinct");
        check(sam.count("b") == 2 && sam.count("bc") == 2 && sam.count("cb") == 1
              && sam.count("abcbc") == 1 && sam.count("ca") == 0, "counts");
        check(sam.firstOccurrence("bc") == 1 && sam.firstOccurrence("cbc") == 2, "first");
        int[] lcs = new SuffixAutomaton("xabcbcy").longestCommonSubstring("zzbcbczz");
        check(lcs[0] == 4 && lcs[1] == 2, "lcs");

        Random rng = new Random(7);
        for (int it = 0; it < 500; it++) {
            String s = randomString(rng, 1, 12), t = randomString(rng, 0, 12);
            SuffixAutomaton a = new SuffixAutomaton(s);
            Set<String> subs = new HashSet<>();
            for (int i = 0; i < s.length(); i++)
                for (int j = i + 1; j <= s.length(); j++) subs.add(s.substring(i, j));
            check(a.distinctSubstrings() == subs.size(), "distinct " + s);
            check(a.len.size() <= Math.max(2, 2 * s.length() - 1), "state bound " + s);
            List<String> probes = new ArrayList<>(subs);
            probes.addAll(List.of("ca", "aaa", "cbcb"));
            for (String p : probes) {
                check(a.contains(p) == subs.contains(p), "contains " + s + " " + p);
                check(a.count(p) == bruteCount(s, p), "count " + s + " " + p);
                check(a.firstOccurrence(p) == s.indexOf(p), "first " + s + " " + p);
            }
            int[] r = a.longestCommonSubstring(t);
            check(r[0] == bruteLcs(s, t) && s.contains(t.substring(r[1], r[1] + r[0])), "lcs " + s + " " + t);
        }
        System.out.println("suffix automaton OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>

class SuffixAutomaton {
public:
    explicit SuffixAutomaton(const std::string& s) {
        newState(0, -1, -1, false);
        for (char c : s) extend(c);
        countOccurrences();
    }

    bool contains(const std::string& p) const { return walk(p) != -1; }

    int count(const std::string& p) const {
        int v = walk(p);
        return v > 0 ? cnt_[v] : 0;
    }

    int firstOccurrence(const std::string& p) const {
        int v = walk(p);
        if (v == -1) return -1;
        return v == 0 ? 0 : first_[v] - (int)p.size() + 1;
    }

    long long distinctSubstrings() const {
        long long total = 0;
        for (int v = 1; v < (int)len_.size(); ++v) total += len_[v] - len_[link_[v]];
        return total;
    }

    // {length, start index in t} of a longest common substring of s and t.
    std::pair<int, int> longestCommonSubstring(const std::string& t) const {
        int v = 0, length = 0, best = 0, bestEnd = -1;
        for (int i = 0; i < (int)t.size(); ++i) {
            char c = t[i];
            while (v != 0 && !next_[v].count(c)) {
                v = link_[v];
                length = len_[v];
            }
            auto it = next_[v].find(c);
            if (it != next_[v].end()) {
                v = it->second;
                ++length;
            }
            if (length > best) {
                best = length;
                bestEnd = i;
            }
        }
        return {best, bestEnd - best + 1};
    }

    int states() const { return (int)len_.size(); }
    int transitions() const {
        int k = 0;
        for (const auto& m : next_) k += (int)m.size();
        return k;
    }
    const std::vector<int>& len() const { return len_; }
    const std::vector<int>& link() const { return link_; }

private:
    int newState(int length, int lnk, int fst, bool clone) {
        next_.emplace_back();
        len_.push_back(length);
        link_.push_back(lnk);
        first_.push_back(fst);
        isClone_.push_back(clone);
        return (int)len_.size() - 1;
    }

    void extend(char c) {
        int cur = newState(len_[last_] + 1, -1, len_[last_], false);
        int p = last_;
        while (p != -1 && !next_[p].count(c)) {        // 1. add the missing c-edges
            next_[p][c] = cur;
            p = link_[p];
        }
        if (p == -1) {
            link_[cur] = 0;                              // 2a. brand-new character
        } else {
            int q = next_[p][c];
            if (len_[p] + 1 == len_[q]) {
                link_[cur] = q;                          // 2b. solid edge
            } else {                                     // 2c. split q with a clone
                int clone = newState(len_[p] + 1, link_[q], first_[q], true);
                next_[clone] = next_[q];                 // copy after newState (it may reallocate)
                while (p != -1) {
                    auto it = next_[p].find(c);
                    if (it == next_[p].end() || it->second != q) break;
                    it->second = clone;
                    p = link_[p];
                }
                link_[q] = clone;
                link_[cur] = clone;
            }
        }
        last_ = cur;
    }

    void countOccurrences() {
        int n = (int)len_.size(), maxLen = len_[last_];
        cnt_.assign(n, 0);
        for (int v = 1; v < n; ++v) cnt_[v] = isClone_[v] ? 0 : 1;
        std::vector<int> bucket(maxLen + 2, 0), order(n);   // counting sort by len
        for (int v = 0; v < n; ++v) bucket[len_[v] + 1]++;
        for (int i = 1; i <= maxLen + 1; ++i) bucket[i] += bucket[i - 1];
        for (int v = 0; v < n; ++v) order[bucket[len_[v]]++] = v;
        for (int i = n - 1; i >= 0; --i) {                  // longest first
            int v = order[i];
            if (link_[v] > 0) cnt_[link_[v]] += cnt_[v];
        }
    }

    int walk(const std::string& p) const {
        int v = 0;
        for (char c : p) {
            auto it = next_[v].find(c);
            if (it == next_[v].end()) return -1;
            v = it->second;
        }
        return v;
    }

    std::vector<std::map<char, int>> next_;
    std::vector<int> len_, link_, first_, cnt_;
    std::vector<bool> isClone_;
    int last_ = 0;
};

static int bruteCount(const std::string& s, const std::string& p) {
    int k = 0;
    for (size_t i = 0; i + p.size() <= s.size(); ++i) k += s.compare(i, p.size(), p) == 0;
    return k;
}

static int bruteLcs(const std::string& s, const std::string& t) {
    int best = 0;
    for (size_t i = 0; i < s.size(); ++i)
        for (size_t j = i + 1; j <= s.size(); ++j)
            if ((int)(j - i) > best && t.find(s.substr(i, j - i)) != std::string::npos) best = (int)(j - i);
    return best;
}

int main() {
    SuffixAutomaton sam("abcbc");
    assert(sam.states() == 8 && sam.transitions() == 9);
    assert((sam.len() == std::vector<int>{0, 1, 2, 3, 4, 1, 5, 2}));
    assert((sam.link() == std::vector<int>{-1, 0, 5, 7, 5, 0, 7, 0}));
    assert(sam.distinctSubstrings() == 12);
    assert(sam.count("b") == 2 && sam.count("bc") == 2 && sam.count("cb") == 1);
    assert(sam.count("abcbc") == 1 && sam.count("ca") == 0);
    assert(sam.firstOccurrence("bc") == 1 && sam.firstOccurrence("cbc") == 2);
    assert((SuffixAutomaton("xabcbcy").longestCommonSubstring("zzbcbczz") == std::make_pair(4, 2)));

    std::mt19937 rng(7);
    auto randomString = [&](int lo, int hi) {
        int n = lo + (int)(rng() % (unsigned)(hi - lo + 1));
        std::string r;
        for (int i = 0; i < n; ++i) r += (char)('a' + rng() % 3);
        return r;
    };
    for (int it = 0; it < 500; ++it) {
        std::string s = randomString(1, 12), t = randomString(0, 12);
        SuffixAutomaton a(s);
        std::set<std::string> subs;
        for (size_t i = 0; i < s.size(); ++i)
            for (size_t j = i + 1; j <= s.size(); ++j) subs.insert(s.substr(i, j - i));
        assert(a.distinctSubstrings() == (long long)subs.size());
        assert(a.states() <= std::max(2, 2 * (int)s.size() - 1));
        std::vector<std::string> probes(subs.begin(), subs.end());
        probes.insert(probes.end(), {"ca", "aaa", "cbcb"});
        for (const std::string& p : probes) {
            assert(a.contains(p) == (subs.count(p) > 0));
            assert(a.count(p) == bruteCount(s, p));
            size_t f = s.find(p);
            assert(a.firstOccurrence(p) == (f == std::string::npos ? -1 : (int)f));
        }
        std::pair<int, int> r = a.longestCommonSubstring(t);
        assert(r.first == bruteLcs(s, t));
        assert(s.find(t.substr(r.second, r.first)) != std::string::npos);
    }
    std::cout << "suffix automaton OK\n";
    return 0;
}
class SuffixAutomaton {
  readonly next: Map<string, number>[] = [];
  readonly len: number[] = [];
  readonly link: number[] = [];
  private first: number[] = []; // end index of the first occurrence
  private isClone: boolean[] = [];
  private cnt: number[] = []; // cnt[v] = |endpos(v)|
  private last = 0;

  constructor(s: string) {
    this.newState(0, -1, -1, new Map(), false);
    for (const c of s) this.extend(c);
    this.countOccurrences();
  }

  private newState(length: number, link: number, first: number, next: Map<string, number>, clone: boolean): number {
    this.next.push(next);
    this.len.push(length);
    this.link.push(link);
    this.first.push(first);
    this.isClone.push(clone);
    return this.len.length - 1;
  }

  private extend(c: string): void {
    const cur = this.newState(this.len[this.last] + 1, -1, this.len[this.last], new Map(), false);
    let p = this.last;
    while (p !== -1 && !this.next[p].has(c)) { // 1. add the missing c-edges
      this.next[p].set(c, cur);
      p = this.link[p];
    }
    if (p === -1) {
      this.link[cur] = 0; // 2a. brand-new character
    } else {
      const q = this.next[p].get(c)!;
      if (this.len[p] + 1 === this.len[q]) {
        this.link[cur] = q; // 2b. solid edge
      } else { // 2c. split q with a clone
        const clone = this.newState(this.len[p] + 1, this.link[q], this.first[q], new Map(this.next[q]), true);
        while (p !== -1 && this.next[p].get(c) === q) {
          this.next[p].set(c, clone);
          p = this.link[p];
        }
        this.link[q] = clone;
        this.link[cur] = clone;
      }
    }
    this.last = cur;
  }

  private countOccurrences(): void {
    const n = this.len.length;
    const maxLen = this.len[this.last];
    this.cnt = this.isClone.map((cl, v) => (v === 0 || cl ? 0 : 1));
    const bucket = new Array<number>(maxLen + 2).fill(0); // counting sort by len
    for (let v = 0; v < n; v++) bucket[this.len[v] + 1]++;
    for (let i = 1; i <= maxLen + 1; i++) bucket[i] += bucket[i - 1];
    const order = new Array<number>(n);
    for (let v = 0; v < n; v++) order[bucket[this.len[v]]++] = v;
    for (let i = n - 1; i >= 0; i--) { // longest first
      const v = order[i];
      if (this.link[v] > 0) this.cnt[this.link[v]] += this.cnt[v];
    }
  }

  private walk(p: string): number {
    let v = 0;
    for (const c of p) {
      const u = this.next[v].get(c);
      if (u === undefined) return -1;
      v = u;
    }
    return v;
  }

  contains(p: string): boolean {
    return this.walk(p) !== -1;
  }

  count(p: string): number {
    const v = this.walk(p);
    return v > 0 ? this.cnt[v] : 0;
  }

  firstOccurrence(p: string): number {
    const v = this.walk(p);
    if (v === -1) return -1;
    return v === 0 ? 0 : this.first[v] - [...p].length + 1;
  }

  distinctSubstrings(): number {
    let total = 0;
    for (let v = 1; v < this.len.length; v++) total += this.len[v] - this.len[this.link[v]];
    return total;
  }

  /** [length, start index in t] of a longest common substring of s and t. */
  longestCommonSubstring(t: string): [number, number] {
    let v = 0, length = 0, best = 0, bestEnd = -1, i = 0;
    for (const c of t) {
      while (v !== 0 && !this.next[v].has(c)) {
        v = this.link[v];
        length = this.len[v];
      }
      const u = this.next[v].get(c);
      if (u !== undefined) {
        v = u;
        length++;
      }
      if (length > best) {
        best = length;
        bestEnd = i;
      }
      i++;
    }
    return [best, bestEnd - best + 1];
  }
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);

function bruteCount(s: string, p: string): number {
  let k = 0;
  for (let i = 0; i + p.length <= s.length; i++) if (s.startsWith(p, i)) k++;
  return k;
}

function bruteLcs(s: string, t: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++)
    for (let j = i + 1; j <= s.length; j++)
      if (j - i > best && t.includes(s.slice(i, j))) best = j - i;
  return best;
}

const sam = new SuffixAutomaton("abcbc");
check(sam.len.length === 8 && sam.next.reduce((k, m) => k + m.size, 0) === 9, "sizes");
check(same(sam.len, [0, 1, 2, 3, 4, 1, 5, 2]), "len");
check(same(sam.link, [-1, 0, 5, 7, 5, 0, 7, 0]), "link");
check(sam.distinctSubstrings() === 12, "distinct");
check(same(["b", "bc", "cb", "abcbc", "ca"].map((p) => sam.count(p)), [2, 2, 1, 1, 0]), "counts");
check(sam.firstOccurrence("bc") === 1 && sam.firstOccurrence("cbc") === 2, "first");
check(same(new SuffixAutomaton("xabcbcy").longestCommonSubstring("zzbcbczz"), [4, 2]), "lcs");

let seed = 7; // small deterministic LCG so runs are reproducible
const rand = (k: number): number => {
  seed = (seed * 1103515245 + 12345) % 2147483648;
  return seed % k;
};
const randomString = (lo: number, hi: number): string => {
  let r = "";
  const n = lo + rand(hi - lo + 1);
  for (let i = 0; i < n; i++) r += "abc"[rand(3)];
  return r;
};
for (let it = 0; it < 500; it++) {
  const s = randomString(1, 12);
  const t = randomString(0, 12);
  const a = new SuffixAutomaton(s);
  const subs = new Set<string>();
  for (let i = 0; i < s.length; i++) for (let j = i + 1; j <= s.length; j++) subs.add(s.slice(i, j));
  check(a.distinctSubstrings() === subs.size, "distinct " + s);
  check(a.len.length <= Math.max(2, 2 * s.length - 1), "state bound " + s);
  for (const p of [...subs, "ca", "aaa", "cbcb"]) {
    check(a.contains(p) === subs.has(p), "contains " + s + " " + p);
    check(a.count(p) === bruteCount(s, p), "count " + s + " " + p);
    check(a.firstOccurrence(p) === s.indexOf(p), "first " + s + " " + p);
  }
  const [best, start] = a.longestCommonSubstring(t);
  check(best === bruteLcs(s, t) && s.includes(t.slice(start, start + best)), "lcs " + s + " " + t);
}
console.log("suffix automaton OK");

Language notes. Python: one dict per state is simple and handles any characters; for around pure Python is slow (several seconds) and memory-hungry, so use flat lists of 26 ints per character or a C extension. Java: HashMap<Character, Integer> boxes everything; for lowercase strings use int[][] next = new int[2 * n][26] (fill with −1) and the clone becomes System.arraycopy. C++: std::map<char, int> keeps edges sorted, which the -th substring walk wants; newState may reallocate the vector, so the clone's edges are copied after it is created rather than through a reference taken before. For speed use std::array<int, 26>. TypeScript: for (const c of s) iterates Unicode code points, so indices are code-point indices; for UTF-16 indices iterate s[i] instead. In every language, the distinct count needs 64-bit arithmetic in general: for it can reach (long in Java, long long in C++; JavaScript numbers are exact up to ).

Real-world uses

Honesty first: in production systems, suffix arrays and FM-indexes dominate full-text indexing (BWA and Bowtie for DNA read alignment, the infini-gram engine over trillion-token corpora); the suffix automaton is more common in theory, competitive programming and specialised matchers. Where it does appear:

  • Pattern matching that skips text: Backward DAWG Matching. BDM (Crochemore, Czumaj, Gąsieniec, Jarominek, Lecroq, Plandowski, Rytter, 1994) builds the suffix automaton of the reversed pattern and reads each text window from right to left; when the automaton dies, the window can shift by more than one character. Its bit-parallel simulation BNDM (Navarro & Raffinot, 1998) is one of the fastest practical exact matchers for medium-length patterns and was used in Navarro's nrgrep.
  • Factor oracles and audio/music. The factor oracle (Allauzen, Crochemore, Raffinot, 1999) is a smaller approximation of the suffix automaton with states. It underlies the Factor Oracle Matching algorithms and IRCAM's OMax/Somax improvisation systems, which learn a musician's phrases and recombine them live.
  • LZ77-style compression analysis. The Lempel–Ziv factorization needs, at each position, the longest previous factor. Walking a suffix automaton of the processed prefix gives it online; textbooks (Crochemore, Hancart & Lecroq 2007) present this as a standard application. Production compressors use hash chains or suffix arrays instead, for constant-factor reasons.
  • Speculative decoding for language models. "SAM Decoding" (Hu et al., 2024, arXiv) builds suffix automata over the generated text and a reference corpus to propose draft continuations by finding the longest matching suffix, the same "longest match ending here" walk as the LCS application above. (Recent research; treat it as an example of the idea, not an industry standard.)
  • Bioinformatics. Suffix automata/DAWGs have been used for repeat finding, motif statistics and maximal unique match detection; the occurrence counts and "longest repeat" queries of this lesson are exactly those operations. Most large-scale tools have moved to compressed suffix arrays for memory reasons.
  • Interviews and contests. The canonical uses: distinct substrings, -th substring, longest common substring of several strings, occurrence statistics. It is a staple of Codeforces and SPOJ hard string problems.

Pitfalls & edge cases

  • Clone with no transitions. The clone must copy 's outgoing edges. Without them, strings like bcb become unreachable.
  • Forgetting to update 's link. After cloning, must become the clone. Forgetting it breaks every later suffix-link walk.
  • Redirect loop condition. Redirect only while the edge points to . Redirecting every -edge on the chain corrupts the automaton.
  • Clone counted as an occurrence. Clones start with .
  • Clone's first occurrence. It is , not the current index.
  • Wrong order for the count propagation. Use decreasing len (counting sort or sort). BFS order of the DAG or state creation order is wrong, because clones are created after their children.
  • LCS length after a link move. Set after moving to ; do not set after following a transition (use ).
  • Empty string. The root represents it. Decide whether queries for "" count (our count("") returns 0 and firstOccurrence("") returns 0, mirroring str.find).
  • Distinct substrings overflow. Up to about : use 64-bit integers.
  • Memory with dense arrays. ints. Allocate states up front (or grow dynamically) and do not forget the clone's copy cost.
  • Array size. At most states for ; for there are 2 states. Allocate .
  • Recursion. The DAG DPs (-th substring, shortest absent string) can be written recursively, but paths can be long: use the len order instead to avoid stack overflow.
  • Multiple strings in one automaton. Concatenating with separators works for some queries but creates substrings across the separator; for "how many of the strings contain " prefer a generalized automaton (see Variations).

Variations

  • Generalized suffix automaton (several strings). Build one automaton for a set of strings by resetting last to the root before each string and handling the case where the transition for cur already exists (it may need cloning). Or insert all strings into a trie and build the automaton over the trie in BFS order. Used for "in how many of the strings does occur" (store, per state, a bitmask or a "last string seen" marker).
  • Suffix automaton of the reversed string = suffix tree. As noted above, the suffix-link tree of the automaton of is the suffix tree of ; this is one of the easiest linear-time suffix tree constructions. See Suffix Trees.
  • Compact DAWG (CDAWG). Merge chains of states with one outgoing edge, like a suffix tree compresses a trie. Blumer et al. (1987, "Complete inverted files for efficient text retrieval and analysis", JACM) describe it; it is smaller than both the suffix tree and the automaton for repetitive text.
  • Factor oracle. An -state automaton that accepts all substrings and a few other strings; much simpler, used in matching and music.
  • Longest common substring of strings. Automaton of the first string; walk each other string, record for each state the best reached, propagate maxima up the suffix-link tree (capped at len), then take the minimum across strings for each state. .
  • Sliding window / deletions. The automaton does not support deleting from the front efficiently in general; for queue-like windows people use two-stack tricks or rebuild, or switch to suffix trees with special support.
  • Persistent / partial queries. Since the construction is online, recording last after each step lets you answer "distinct substrings of the prefix of length " or "does occur in the first characters" (with first-occurrence data) offline.

Comparison with suffix arrays and suffix trees

Suffix automatonSuffix array + LCPSuffix tree
What it storesEndpos classes (≤ 2n − 1 states, ≤ 3n − 4 edges)Sorted suffix start positions + LCP of neighboursCompressed trie of all suffixes (≤ 2n nodes)
Build online (fixed alphabet) simple, with SA-IS with Ukkonen (online) or from the automaton of
Memory in practiceModerate: ~ states with edge mapsSmallest: – ints per characterLargest: 10–20+ bytes per character
Substring check (or with LCP tricks)
Distinct substringsSum over statesSum of edge lengths
Sorted order, -th suffix, LCP of two suffixesNot directly (-th substring via path counting)NativeDFS order
LCS of two strings walk, automaton of one string onlySA of Generalized suffix tree
Online appendYes, nativelyNoYes (Ukkonen)
Code size~25 lines~30–60 lines100+ lines (Ukkonen)

When to choose which: if you need sorted suffixes, LCP queries, or the smallest memory, use Suffix Arrays. If you need online appends, occurrence counts, or LCS with a second string, the automaton is shortest to write. Suffix Trees give all of the above at a higher memory and code cost, and you can get one from the automaton of the reversed string.

Practice ladder

Each problem is described in my own words; follow the link for the statement. The solutions use this compact builder, which returns the transitions, len, link, occurrence counts, first-occurrence end positions, and the states in decreasing len order. Every solution below was cross-checked against brute force on 2,000 random strings.

def build(s):
    """Suffix automaton. Returns nxt, ln, link, cnt (occurrences), first (end of first occurrence),
    and the states sorted by len descending (children of the link tree before parents)."""
    nxt, ln, link, first, cnt = [{}], [0], [-1], [-1], [0]
    last = 0
    for i, c in enumerate(s):
        cur = len(ln)
        nxt.append({}); ln.append(ln[last] + 1); link.append(-1); first.append(i); cnt.append(1)
        p = last
        while p != -1 and c not in nxt[p]:
            nxt[p][c] = cur
            p = link[p]
        if p == -1:
            link[cur] = 0
        else:
            q = nxt[p][c]
            if ln[p] + 1 == ln[q]:
                link[cur] = q
            else:
                cl = len(ln)
                nxt.append(dict(nxt[q])); ln.append(ln[p] + 1); link.append(link[q])
                first.append(first[q]); cnt.append(0)
                while p != -1 and nxt[p].get(c) == q:
                    nxt[p][c] = cl
                    p = link[p]
                link[q] = link[cur] = cl
        last = cur
    order = sorted(range(len(ln)), key=lambda v: -ln[v])
    for v in order:
        if link[v] > 0:
            cnt[link[v]] += cnt[v]
    return nxt, ln, link, cnt, first, order

1. Number of Distinct Substrings in a String (LeetCode 1698) — Count the distinct non-empty substrings of a string. (Premium.) Teaches the main formula.

Hint

sum(ln[v] - ln[link[v]] for v in range(1, len(ln))). The follow-up asks for better than ; this is .

2. Distinct Substrings (CSES 2105) — The same count for up to . Teaches that the answer needs 64-bit integers.

Hint

Same formula. In C++ or Java use a dense [26] array per state and a long accumulator.

3. Repeating Substring (CSES 2106) — Find a longest substring that occurs at least twice, or report that none exists. Teaches plus to reconstruct the string.

Solution
def longest_repeat(s):
    nxt, ln, link, cnt, first, order = build(s)
    best = max((v for v in range(1, len(ln)) if cnt[v] >= 2), key=lambda v: ln[v], default=0)
    if best == 0:
        return ""
    end = first[best]
    return s[end - ln[best] + 1:end + 1]


assert longest_repeat("banana") == "ana" and longest_repeat("abcd") == ""
assert longest_repeat("cabababc") == "abab"

The state with the largest len among those with holds the answer as its longest string; its first occurrence ends at . after building.

4. Longest Duplicate Substring (LeetCode 1044) — The same task on LeetCode (return any longest repeated substring, or an empty string). Teaches recognizing a known problem in disguise; the common alternative is binary search plus rolling hash.

Hint

longest_repeat from problem 3, unchanged. Compare with the String Hashing solution: expected, versus deterministic here.

5. Maximum Length of Repeated Subarray (LeetCode 718) — Longest common contiguous subarray of two integer arrays. Teaches that the automaton works over any alphabet, including integers.

Hint

Build the automaton of one array (dict transitions keyed by integers) and run the LCS walk with the other. The usual solution is an DP (see String DP); this is .

6. Longest Common Substring (SPOJ LCS) — Longest common substring of two strings of length up to 250,000. Teaches the walk where DP is too slow.

Hint

The longestCommonSubstring method from the implementation. The harder sibling, SPOJ LCS2, asks for up to 10 strings: see "Longest common substring of strings" in Variations.

7. Substring Order I (CSES 2108) — The -th smallest distinct substring. Teaches path counting in the DAG.

Solution
def kth_distinct(s, k):
    nxt, ln, link, cnt, first, order = build(s)
    paths = [1] * len(ln)                # 1 for stopping here + all longer continuations
    for v in order:                      # longest first is a reverse topological order of the DAG
        paths[v] += sum(paths[u] for u in nxt[v].values())
    v, out = 0, []
    while k > 0:
        for c in sorted(nxt[v]):
            u = nxt[v][c]
            if k <= paths[u]:
                out.append(c); v = u; k -= 1   # the string itself uses up one
                break
            k -= paths[u]
    return "".join(out)


assert kth_distinct("babaacbaab", 10) == "aba"
assert kth_distinct("abcbc", 7) == "bc"

order (decreasing len) is a reverse topological order of the transition DAG, because every transition goes to a state of larger len. Checked: kth_distinct("babaacbaab", 10) == "aba".

8. Substring Order II (CSES 2109) — The -th smallest substring when substrings are counted with multiplicity. Teaches weighting paths by .

Solution
def kth_with_repeats(s, k):
    nxt, ln, link, cnt, first, order = build(s)
    total = [0] * len(ln)
    for v in order:
        total[v] = (cnt[v] if v else 0) + sum(total[u] for u in nxt[v].values())
    v, out = 0, []
    while True:
        for c in sorted(nxt[v]):
            u = nxt[v][c]
            if k <= total[u]:
                out.append(c); v = u; k -= cnt[u]   # the cnt[u] copies of this string come first
                break
            k -= total[u]
        if k <= 0:
            return "".join(out)


assert kth_with_repeats("baabaa", 7) == "aab"

Each string of state appears times in the multiset, so "stop here" consumes instead of 1. Example: the 7th smallest substring of baabaa counted with repetition is aab.

9. Substring Distribution (CSES 2110) — For every length , the number of distinct substrings of length . Teaches the interval view of a state.

Solution
def substring_distribution(s):
    nxt, ln, link, cnt, first, order = build(s)
    diff = [0] * (len(s) + 2)
    for v in range(1, len(ln)):
        diff[ln[link[v]] + 1] += 1          # lengths minlen..len each gain one string
        diff[ln[v] + 1] -= 1
    res, run = [], 0
    for k in range(1, len(s) + 1):
        run += diff[k]; res.append(run)
    return res


assert substring_distribution("abab") == [2, 2, 2, 1]

State contains exactly one string of each length in . A difference array adds all intervals in . For abab: 2, 2, 2, 1.

10. Fake News (hard) (Codeforces 802I) — Sum, over all distinct substrings , of the square of the number of occurrences of . Teaches "group by state" sums.

Solution
def self_similarity(s):
    nxt, ln, link, cnt, first, order = build(s)
    return sum(cnt[v] ** 2 * (ln[v] - ln[link[v]]) for v in range(1, len(ln)))


assert [self_similarity(s) for s in ["aa", "abcd", "ccc", "abcc"]] == [5, 10, 14, 12]

All strings of state have occurrences. Checked on the small cases aa → 5, abcd → 10, ccc → 14, abcc → 12.

11. String (Codeforces 123D) — Sum over distinct substrings of . Teaches the same pattern with a different .

Hint

Replace cnt[v] ** 2 in problem 10 by cnt[v] * (cnt[v] + 1) // 2.

12. Forbidden Indices (Codeforces 873F) — Maximize times the number of occurrences of that end at an allowed index. Teaches changing what the initial counts mean.

Hint

Initialize only if index is allowed; propagate as usual; answer (the longest string of a state is the best of its class).

13. Match & Catch (Codeforces 427D) — Shortest string that occurs exactly once in each of two strings. Teaches combining counts from two strings.

Hint

Build a generalized automaton (or one for ) and keep two count arrays, one per string. A state with both counts equal to 1 offers its shortest string, of length ; take the minimum over such states. The suffix-array solution is the classic alternative.

14. Cyclical Quest (Codeforces 235C) — For each query string , count occurrences in of all distinct rotations of . Teaches the LCS walk with a sliding left end.

Hint

Walk (minus the last character) through the automaton, keeping as in LCS. Whenever , move up while (setting after each move), so that is the state of the last characters; then add unless was already counted for this query (equal rotations land in the same state).

Common mistakes & interview follow-ups

"What is a state?" A set of substrings with the same set of end positions. They are suffixes of one another with consecutive lengths .

"Why at most states?" Each appended character adds cur and at most one clone, and the first two characters add no clone. Or: clones are internal nodes with at least two children in a tree whose leaves-and-prefix-nodes are the prefix states.

"Why is the construction linear if the loops can be long?" The first loop creates a transition each iteration (at most in total); the redirect loop is paid for by the depth of last in the suffix-link tree, which rises by at most 3 per character and falls by 1 per iteration.

"Why clone instead of just adding an edge?" Because the target state mixes strings that now have different end-position sets. A DFA state must have one future; the clone separates the strings that just gained the new end position.

"How would you count occurrences of a pattern?" 1 for every prefix state, 0 for clones, add up the suffix-link tree in decreasing len, then walk the pattern and read .

"Suffix automaton or suffix array?" Array for sorted order, LCP queries and memory; automaton for online construction, counts and two-string LCS. Being able to explain both, and that the automaton of the reversed string gives the suffix tree, is a strong answer.

"What about the alphabet?" Dense arrays are per step but cost ints per state (208 MB for , ); maps cost per step and memory overall.

Mistakes interviewers watch for: clone without copied transitions; forgetting $\text{link}(q) = $ clone; redirecting edges that do not point to ; counting clones as occurrences; propagating counts in creation order instead of decreasing len; using as the matched length in the LCS walk; 32-bit overflow in the distinct count.

Quick quiz

1. In the automaton of abcbc, which state holds bcb, and what are its len and minlen?

Answer

State 4, which holds cb, bcb, abcb. len = 4, link = 5 with len 1, so minlen = 2.

2. Build the automaton of aa by hand. How many states, and is there a clone?

Answer

Three states: root, a (len 1), aa (len 2). Step 2 walks from state 1 (no a-edge, add 1 →a→ 2), then to the root, which has an a-edge to state 1 with len(0) + 1 = 1 = len(1): solid, so link(2) = 1. No clone. Distinct substrings: .

3. For abb, how many states does the suffix automaton have, and which step clones?

Answer

5 states. Step 3 (second b): the walk from ab adds ab →b→ abb and reaches the root, whose b-edge goes to the state of ab (len 2), not solid (len(0) + 1 = 1). Clone a state for b (len 1). This matches the bound for .

4. Why are the occurrence counts propagated in decreasing order of len rather than in the order states were created?

Answer

A count must be pushed from a state to its link only after the state has received all counts from its own children in the suffix-link tree. Children have strictly larger len than their parent, so decreasing len is a safe order. Creation order is not: a clone is created after the state it splits, yet it is that state's parent.

5. Your automaton uses int[26] per state and . Estimate the memory for the transition table alone.

Answer

Up to states × 26 × 4 bytes ≈ 208 MB. Use maps or sorted edge lists, or cap the alphabet.

Further reading / sources

  • A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, J. Seiferas, "The smallest automaton recognizing the subwords of a text", Theoretical Computer Science 40:31–55, 1985 — the original DAWG paper: linear-time online construction and the / bounds.
  • A. Blumer, J. Blumer, D. Haussler, R. McConnell, A. Ehrenfeucht, "Complete inverted files for efficient text retrieval and analysis", Journal of the ACM 34(3):578–595, 1987 — the compact DAWG.
  • M. Crochemore, "Transducers and repetitions", Theoretical Computer Science 45:63–86, 1986 — suffix automata and longest common factors in linear time.
  • M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2007, ch. 5 (indexes, suffix and factor automata).
  • D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997 — the suffix tree view and applications.
  • cp-algorithms, Suffix Automaton — the notation of this lesson (len, link, clone), proofs of the bounds and of linearity, and a long list of applications.
  • M. Crochemore, A. Czumaj, L. Gąsieniec, S. Jarominek, T. Lecroq, W. Plandowski, W. Rytter, "Speeding up two string-matching algorithms", Algorithmica 12:247–267, 1994 — Backward DAWG Matching.
  • G. Navarro, M. Raffinot, "A bit-parallel approach to suffix automata: fast extended string matching", CPM 1998 — BNDM.
  • C. Allauzen, M. Crochemore, M. Raffinot, "Factor oracle: a new structure for pattern matching", SOFSEM 1999.

Previous lesson: Suffix Arrays & LCP · Next lesson: Suffix Trees

Related: String Algorithms overview · KMP & the Prefix Function · Aho–Corasick · String Hashing in Depth · Tries · Topological Sort · DAG DP · Course home