YO DAWG!! - Suffix Automaton Explainer

📖 WHAT IS A DAWG???!

A Directed Acyclic Word Graph (also called a Suffix Automaton) is a minimal finite automaton that accepts every suffix of a word — and therefore every substring. It is the smallest possible structure that can recognise all substrings of a word.

Unlike a trie, which stores each suffix separately, the DAWG merges states that accept the same set of future suffixes into a single node. The result has at most 2n − 1 states and 3n − 4 transitions for a word of length n.

What can you do with it? After building the DAWG for string S, you can find the Longest Common Substring between S and any query string T in O(|T|) time by traversing the automaton.

🧠 Key Concepts

State: A node representing one endpos-equivalence class. All strings in a state have lengths in a contiguous range [link.len + 1 … len(u)], and they all occur at exactly the same ending positions.
Transition: A labelled directed edge. Following edge labelled c from state u means "I just read character c, and I'm now in the class of strings that end with c".
Suffix Link: A dashed edge from state u to the state whose endpos is the smallest superset of endpos(u). Concretely: the state representing the longest proper suffix of u's shortest string. Because a shorter string must occur at least as often, its endpos is always a superset.
len(u): The length of the longest string in state u's equivalence class. The invariant len(link(u)) < len(u) always holds, making the suffix-link tree well-founded.
endpos(u): The set of ending positions in the original word where the strings in state u occur. Two substrings share a state if and only if they end at exactly the same positions — this partition into endpos-equivalence classes is the key idea behind the whole structure.

⚙️ ENTER YOUR WORD!!!

Type a short word (2–25 lowercase letters). We will build the DAWG for it step by step!

🔨 STEP-BY-STEP CONSTRUCTION!!!

Tap Next ▶ to walk through the algorithm one operation at a time. Blue border = newly added this step. Orange border = modified this step. Dashed arrows = suffix links.

🔎 Pinch or Ctrl+scroll to zoom · drag to pan · use ⤢ to fit

Step 0 / 0

Press Next ▶ to begin.

📋 Show full pseudocode

# Initialise once before processing any characters:
last = root = new_state(); root.len = 0; root.link = NULL

# Call sa_extend(c) for each character c in the word, left to right.
# 'last' is an implicit in/out variable updated at the end of each call.

sa_extend(c):
    cur       = new_state()
    cur.len   = last.len + 1
    p         = last
    while p != NULL and p.next[c] is undefined:
        p.next[c] = cur        # walk up suffix links, adding transitions
        p = p.link
    if p == NULL:
        cur.link = root        # 'c' is brand new in the word so far
    else:
        q = p.next[c]
        if p.len + 1 == q.len:
            cur.link = q       # q is already the minimal representative
        else:
            clone      = new_state()
            clone.len  = p.len + 1
            clone.link = q.link          # inherit q's suffix-link parent
            clone.next = copy(q.next)    # inherit q's transitions
            while p != NULL and p.next[c] == q:
                p.next[c] = clone        # redirect short-suffix paths to clone
                p = p.link
            q.link   = clone
            cur.link = clone
    last = cur

🔍 FIND THE LCS!!!

The DAWG is built! Enter any query word to find its Longest Common Substring with the original word — no rebuild needed, try as many queries as you like!

🏃 TRAVERSAL & LCS!!!

We now walk the query word through the completed DAWG character by character. At each step we either follow a transition directly, or backtrack up suffix links until we can. The longest stretch without needing to reset is the Longest Common Substring.

🔎 Pinch or Ctrl+scroll to zoom · drag to pan · use ⤢ to fit

Step 0 / 0

Press Next ▶ to begin.

Current best LCS: — (length 0)

📋 Show LCS traversal pseudocode

# Given: the completed DAWG (root, transitions, suffix links)
# Input: query string T
# Output: longest substring common to the base word and T

lcs_query(T):
    v = root   # current DAWG state
    l = 0      # current match length
    best_l = 0; best_end = -1

    for i, c in enumerate(T):
        # Backtrack until we can follow c (or reach root)
        while v != root and v.next[c] is undefined:
            v = v.link
            l = v.len   # longest match this state can guarantee

        if v.next[c] is defined:
            v = v.next[c]
            l = l + 1
        # else: c absent from base word entirely; v=root, l stays 0

        if l > best_l:
            best_l = l
            best_end = i

    return T[best_end - best_l + 1 : best_end + 1]