Suffix Automaton (SAM)

Wiki › Thuật toán › Thuật toán xâu

huunguyen · Last updated 8, Tháng 4, 2026, 16:02

Suffix Automaton (SAM) là automaton hữu hạn nhỏ nhất chấp nhận tất cả các suffix của xâu $s$ . Nó lưu trữ tất cả chuỗi con phân biệt của $s$ trong $O (N)$ node và $O (N)$ thời gian xây dựng — mạnh hơn Suffix Array cho nhiều bài toán.

Tính chất: SAM có tối đa $2 N - 1$ node và $3 N - 4$ cạnh.

Ứng dụng:

Đếm số chuỗi con phân biệt.
Tìm chuỗi con chung dài nhất (LCS) của nhiều xâu.
Đếm số lần xuất hiện của mỗi chuỗi con.
Tìm chuỗi con nhỏ thứ $k$ theo thứ tự từ điển.

Cấu trúc

Mỗi node của SAM đại diện cho một tập endpos — tập vị trí kết thúc của một nhóm chuỗi con tương đương. Mỗi node lưu:

len: độ dài chuỗi dài nhất trong nhóm.
link: suffix link — trỏ đến node đại diện cho nhóm suffix link (endpos lớn hơn).
next[c]: chuyển trạng thái khi đọc ký tự $c$ .

Cài đặt

struct SuffixAutomaton {
    struct State {
        int len, link;
        map<char, int> next;
        long long cnt;   // số lần xuất hiện (endpos size)
    };

    vector<State> st;
    int last;

    SuffixAutomaton() {
        st.push_back({0, -1, {}, 0});
        last = 0;
    }

    void extend(char c) {
        // Kiểm tra đã có chuyển tiếp chưa (online extension)
        if (st[last].next.count(c)) {
            int q = st[last].next[c];
            if (st[q].len == st[last].len + 1) {
                last = q;
                return;
            }
            int clone = st.size();
            st.push_back({st[last].len + 1, st[q].link, st[q].next, 0});
            while (last != -1 && st[last].next[c] == q) {
                st[last].next[c] = clone;
                last = st[last].link;
            }
            st[q].link = clone;
            last = clone;
            return;
        }

        int cur = st.size();
        st.push_back({st[last].len + 1, -1, {}, 1});
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) st[cur].link = 0;
        else {
            int q = st[p].next[c];
            if (st[q].len == st[p].len + 1) st[cur].link = q;
            else {
                int clone = st.size();
                st.push_back({st[p].len + 1, st[q].link, st[q].next, 0});
                while (p != -1 && st[p].next.count(c) && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = clone;
                st[cur].link = clone;
            }
        }
        last = cur;
    }

    void build(const string& s) {
        for (char c : s) extend(c);
    }

    // Tính số lần xuất hiện của mỗi chuỗi con (endpos size)
    // Cần topological sort theo len giảm dần
    void calc_cnt() {
        int n = st.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            return st[a].len > st[b].len;
        });
        for (int v : order)
            if (st[v].link != -1)
                st[st[v].link].cnt += st[v].cnt;
    }
};

Ứng dụng 1: Đếm chuỗi con phân biệt

SuffixAutomaton sam;
sam.build(s);
long long ans = 0;
for (int i = 1; i < (int)sam.st.size(); i++)
    ans += sam.st[i].len - sam.st[sam.st[i].link].len;
// Mỗi node đóng góp (len[v] - len[link[v]]) chuỗi con phân biệt

Ứng dụng 2: Chuỗi con chung dài nhất (LCS)

// Xây SAM cho s1, sau đó duyệt s2 trên SAM
SuffixAutomaton sam;
sam.build(s1);

int cur = 0, cur_len = 0, lcs = 0;
for (char c : s2) {
    while (cur != 0 && !sam.st[cur].next.count(c)) {
        cur = sam.st[cur].link;
        cur_len = sam.st[cur].len;
    }
    if (sam.st[cur].next.count(c)) {
        cur = sam.st[cur].next[c];
        cur_len++;
    }
    lcs = max(lcs, cur_len);
}

Ứng dụng 3: Chuỗi con nhỏ thứ $k$

// Tính số đường đi từ mỗi node đến trạng thái cuối (dp[v])
// Duyệt tham lam: tại mỗi node, đi theo cạnh nhỏ nhất sao cho dp[next] >= k

So sánh Suffix Array vs SAM

	Suffix Array	Suffix Automaton
Build	$O (N \log N)$	$O (N)$
Bộ nhớ	$O (N)$	$O (N \cdot Σ)$
LCS nhiều xâu	Phức tạp	Tự nhiên
Đếm chuỗi con phân biệt	Dùng LCP	Tự nhiên
Cài đặt	Trung bình	Phức tạp

Khi nào dùng SAM?

Bài toán đòi hỏi thao tác linh hoạt trên tất cả chuỗi con của xâu.
LCS của nhiều xâu (xây SAM cho xâu thứ nhất, duyệt các xâu còn lại).
Đếm số lần xuất hiện của nhiều pattern trong một text.

Bình luận

Không có bình luận tại thời điểm này.