Suffix Automaton Construction and Applications in String Matching

A suffix automaton is a linear-size directed acyclic graph that represents all substrings of a string, enabling linear-time solutions for pattern matching, distinct substring counting, and longest common substring problems.

The shareOI repository by hzwer is a curated collection of algorithmic teaching materials used in competitive programming training. Among its comprehensive coverage of string algorithms, the repository contains detailed lecture slides on suffix automaton construction and its practical applications in string matching scenarios.

What Is a Suffix Automaton?

A suffix automaton (SAM) is a minimal deterministic finite automaton that recognizes all suffixes of a given string. For a string S of length n, the automaton contains at most 2n - 1 states and 3n - 4 transitions, making it remarkably space-efficient compared to suffix trees or arrays.

Each state in the automaton represents an endpos-equivalence class—a set of substrings that occur at the same set of ending positions in the original string. The automaton maintains two critical properties: it is state-minimal (no two states recognize the same set of substrings), and it can be constructed in O(n) time using online algorithms.

Suffix Automaton Construction Algorithm

The linear-time construction algorithm processes the string character by character, extending the automaton incrementally. This approach, detailed in 字符串/后缀自动机_陈立杰.pptx, maintains the invariant that after processing the first i characters, the automaton recognizes exactly all substrings of the prefix S[0..i-1].

State Structure and Transitions

Each state v stores three essential components:

• len[v]: The maximum length of strings in the equivalence class represented by v
• link[v]: The suffix link pointing to the state representing the longest proper suffix of the strings in v
• next[v]: A map (or array) of transitions, where next[v][c] gives the state reached by appending character c

The root state (index 0) has len = 0 and link = -1, serving as the entry point for all substring traversals.

The Extension Operation

When extending the automaton with a new character c, the algorithm creates a new state cur with len[cur] = len[last] + 1, where last is the state representing the entire current string. It then traverses suffix links from last, adding transitions for c until it finds a state that already has a transition for c or reaches the root.

If no such transition exists, link[cur] is set to the root. If a transition exists to state q, and len[q] = len[p] + 1 (where p is the state with the existing transition), then link[cur] = q. Otherwise, a clone state is created to maintain the state-minimal property, copying q's transitions and suffix link but with len[clone] = len[p] + 1.

Implementation in C++

The following implementation follows the algorithmic details from 后缀自动机_陈立杰.pptx and provides a complete, runnable C++14 solution for suffix automaton construction.

// C++14 – Linear-time suffix automaton construction
#include <bits/stdc++.h>
using namespace std;

struct State {
    int len = 0;                     // max length of strings in this class
    int link = -1;                   // suffix link
    unordered_map<char, int> next;   // transitions
};

const int MAXN = 100000;             // maximum string length
vector<State> st(2 * MAXN);
int sz = 1;                          // current size (states 0..sz-1)
int last = 0;                        // state representing whole string

void sa_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p = last;
    
    // Add transition p --c--> cur for all suffixes without transition c
    while (p != -1 && !st[p].next.count(c)) {
        st[p].next[c] = cur;
        p = st[p].link;
    }
    
    if (p == -1) {
        st[cur].link = 0;  // link to root
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            // Clone state
            int clone = sz++;
            st[clone] = st[q];  // copy transitions and link
            st[clone].len = st[p].len + 1;
            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

Applications in String Matching

The suffix automaton enables several fundamental string operations in linear time. The lecture materials in 字符串/后缀自动机_陈立杰.pptx detail these applications with mathematical proofs and complexity analysis.

Pattern Occurrence Detection

To determine if a pattern P occurs in the original text S, traverse the automaton starting from the root, following transitions labeled by characters of P. If at any point a required transition is missing, the pattern does not occur. If the traversal completes, the pattern appears at least once.

bool contains(const string& pattern) {
    int v = 0;  // start at root
    for (char c : pattern) {
        if (!st[v].next.count(c)) return false;
        v = st[v].next[c];
    }
    return true;  // pattern occurs in original string
}

This operation runs in O(|P|) time, independent of the text length.

Counting Distinct Substrings

The suffix automaton provides a direct formula for counting distinct substrings. For each state v (excluding the root), the number of distinct substrings represented by paths ending in v equals len[v] - len[link[v]]. Summing this over all states yields the total number of distinct substrings.

long long distinct_substrings() {
    long long ans = 0;
    for (int i = 1; i < sz; ++i)  // skip root (i = 0)
        ans += st[i].len - st[st[i].link].len;
    return ans;
}

This computation runs in O(|S|) time, making it significantly faster than suffix array-based approaches that typically require O(|S| log |S|) or O(|S|) with more complex implementations.

Longest Common Substring

To find the longest common substring between two strings S (used to build the automaton) and T (the query string), traverse the automaton with T while maintaining the current match length. When a transition exists, increment the match length; when it fails, follow suffix links and adjust the length accordingly, tracking the maximum value encountered.

This algorithm runs in O(|S| + |T|) time, providing optimal complexity for the longest common substring problem.

Educational Resources in shareOI

The hzwer/shareoi repository organizes its teaching materials by algorithmic category, with string algorithms located in the 字符串/ directory. The suffix automaton implementation and theory are primarily covered in:

• 字符串/后缀自动机_陈立杰.pptx – Comprehensive lecture slides covering linear-time construction, state minimality proofs, and the three primary applications detailed above. The slides include visual diagrams of state splitting and suffix link formation during the extension operation.

• 字符串/后缀数组——处理字符串的有力工具_罗穗骞.ppt – Comparative material showing the relationship between suffix arrays and automata, useful for understanding when to prefer each data structure based on memory constraints and query patterns.

• 字符串/HASH函数及其应用_朱全民.ppt – Rolling hash techniques that complement suffix automata in hybrid string matching solutions, particularly useful for probabilistic pattern matching with lower constant factors.

These resources follow the repository's convention of using PowerPoint and PDF formats for lecture delivery, requiring no compilation or build steps—contributors simply add new slide files to the appropriate category folder.

Summary

• Suffix automaton construction builds a state-minimal deterministic finite automaton recognizing all substrings of a text in O(n) time using online extension operations.
• The implementation in hzwer/shareoi uses a state structure with len, link, and transition map, handling state cloning when necessary to maintain minimality.
• Pattern matching runs in O(m) time by traversing transitions; distinct substring counting uses the formula len[v] - len[link[v]] summed over all states.
• The longest common substring problem solves in O(|S| + |T|) by traversing the automaton of one string with the other.
• Educational materials in 字符串/后缀自动机_陈立杰.pptx provide the theoretical foundation and visual explanations for these algorithms.

Frequently Asked Questions

What is the time complexity of suffix automaton construction?

The construction algorithm runs in O(n) linear time, where n is the length of the input string. Each character extension performs a constant amount of work amortized over the entire construction, including the occasional state cloning operation required to maintain the automaton's minimality.

How does a suffix automaton compare to a suffix array for string matching?

A suffix automaton typically uses O(n) memory (at most 2n-1 states) and supports O(m) pattern queries, whereas suffix arrays use O(n) memory but require O(m log n) or O(m) with additional structures (LCP array + RMQ) for pattern matching. Suffix automata excel when you need to query multiple patterns against a single static text, while suffix arrays are often preferred for space-critical applications or when lexicographical ordering is required.

Can suffix automata handle multiple strings or only single text construction?

While the standard construction algorithm builds an automaton for a single string, you can extend the structure to handle multiple strings by either concatenating strings with unique separator characters (building one automaton) or building separate automata for each string. The hzwer/shareoi materials demonstrate the single-string construction, which is the foundation for solving multi-string problems like longest common substring between two different texts.

Where can I find the theoretical proofs for the linear time construction?

The complete mathematical proofs for the linear time bound, state minimality, and correctness of the extension algorithm are contained in 字符串/后缀自动机_陈立杰.pptx within the hzwer/shareoi repository. These slides provide visual step-by-step demonstrations of state splitting, suffix link formation, and the amortized analysis that guarantees O(n) construction time.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}