Wiki › Thuật toán › Thuật toán xâu › Suffix Automaton (SAM)

Suffix Automaton (SAM)

huunguyen Updated Tháng sáu 2, 2026

Suffix Automaton (SAM) — automaton hậu tố — là automaton hữu hạn xác định (DFA) nhỏ nhất chấp nhận đúng tập tất cả hậu tố (suffix) của một xâu $s$ . Điều kỳ diệu là: dù một xâu độ dài $N$ có thể có tới $O (N^{2})$ xâu con phân biệt, SAM nén toàn bộ chúng vào chỉ $O (N)$ đỉnh và xây dựng online (thêm từng ký tự) trong $O (N \cdot | Σ |)$ — thay vì $O (N^{2})$ của cách liệt kê thô. Nhờ đó các bài như đếm xâu con phân biệt, tìm xâu con chung dài nhất (LCS), đếm số lần xuất hiện của mẫu... đều giải được trong thời gian gần tuyến tính.

Tính chất kích thước: với $N \geq 2$ , SAM có tối đa $2 N - 1$ đỉnh và $3 N - 4$ cạnh. Đây là chặn chặt, rất hữu ích để cấp phát bộ nhớ.

Ý tưởng / Trực giác

Mỗi đỉnh = một lớp tương đương theo endpos

Với một xâu con $t$ của $s$ , gọi $endpos (t)$ là tập tất cả vị trí kết thúc của $t$ trong $s$ . Ví dụ $s = abcbc$ thì $endpos (bc) = {3, 5}$ (đánh số từ 1).

Quan sát then chốt: rất nhiều xâu con có cùng tập endpos. Trong ví dụ trên, $bc$ và $c$ đều kết thúc đúng tại ${3, 5}$ . SAM gom mọi xâu con có cùng endpos vào một đỉnh duy nhất. Có thể chứng minh số tập endpos phân biệt $\leq 2 N - 1$ , nên số đỉnh là $O (N)$ — đó là lý do SAM "nén" được toàn bộ $O (N^{2})$ xâu con.

Các xâu con cùng một lớp endpos có một cấu trúc đẹp: chúng là một dải độ dài liên tiếp $[minlen, len]$ , và xâu ngắn hơn luôn là hậu tố của xâu dài hơn. Mỗi đỉnh $v$ chỉ cần lưu $len (v)$ = độ dài xâu dài nhất trong lớp.

Suffix link — "rút ngắn để nhảy sang lớp khác"

Lấy xâu dài nhất của lớp $v$ rồi bỏ dần ký tự đầu, đến lúc nào đó endpos sẽ "to ra" và ta rơi sang một lớp khác $w$ . Cạnh $link (v) \to w$ gọi là suffix link. Các suffix link tạo thành một cây gốc tại đỉnh khởi đầu $t_{0}$ (lớp của xâu rỗng). Tính chất:

$minlen (v) = len (link (v)) + 1 .$

Nghĩa là lớp $v$ chứa đúng $len (v) - len (link (v))$ xâu con phân biệt. Đây là công thức xương sống của hầu hết ứng dụng.

Vì sao việc thêm ký tự lại đúng?

Khi thêm ký tự $c$ , ta tạo đỉnh mới $c u r$ cho hậu tố dài nhất mới (cả xâu $s + c$ ). Sau đó đi theo suffix link từ $l a s t$ và nối cạnh $c$ tới $c u r$ cho mọi đỉnh chưa có cạnh $c$ — đó chính là các hậu tố của $s$ chưa từng được theo sau bởi $c$ . Khi gặp đỉnh $p$ đã có cạnh $c \to q$ , có hai khả năng:

Nếu $len (q) = len (p) + 1$ : $q$ đã đúng là lớp cần nối, đặt $link (c u r) = q$ , xong.
Nếu không: lớp $q$ bị "lẫn" cả xâu dài lẫn xâu ngắn hơn nhưng giờ endpos của chúng tách nhau. Ta phải clone (tách) $q$ thành đỉnh $c l o n e$ giữ phần ngắn, rồi sửa lại các cạnh trỏ về. Bước clone chính là chỗ đảm bảo automaton vẫn tối thiểu.

Ví dụ chạy tay: xây SAM cho `aba`

Đỉnh khởi đầu $0$ có $len = 0, link = - 1$ . Ta thêm lần lượt a, b, a.

Thêm a → tạo đỉnh $1$ , $len = 1$ . Từ $l a s t = 0$ nối cạnh a rồi $p$ thành $- 1$ ⇒ $link (1) = 0$ . last = 1.

        a
   (0) ----> (1)        len: 0  1
                        link:-1  0

Thêm b → tạo đỉnh $2$ , $len = 2$ . Từ $l a s t = 1$ và $0$ đều chưa có cạnh b, nối b → 2; $p = - 1$ ⇒ $link (2) = 0$ . last = 2.

        a        b
   (0) ----> (1) ----> (2)     len: 0 1 2
     \________________/        link:-1 0 0
              b

Thêm a (ký tự lặp lại — đây là chỗ phát sinh clone) → tạo đỉnh $3$ , $len = 3$ . Đi từ $l a s t = 2$ :

$p = 2$ : chưa có cạnh a, nối $2 \overset{a}{\to} 3$ , nhảy $p = link (2) = 0$ .
p=0: đã có cạnh 0→a1, đặt q=1.
- Kiểm tra $len (q = 1) = 1$ và $len (p = 0) + 1 = 1$ ⇒ bằng nhau ⇒ không cần clone. Đặt $link (3) = 1$ .

last = 3. Kết quả cuối:

        a        b        a
   (0) ----> (1) ----> (2) ----> (3)
     \        |________________/
      \ b           a (từ 2)
       \___________________________ (2 -a-> 3)

  đỉnh : 0   1   2   3
  len  : 0   1   2   3
  link :-1   0   0   1

Kiểm chứng bằng công thức $len (v) - len (link (v))$ :

đỉnh $v$	len	link	đóng góp xâu con phân biệt
1	1	0	$1 - 0 = 1$ → `a`
2	2	0	$2 - 0 = 2$ → `b`, `ab`
3	3	1	$3 - 1 = 2$ → `ba`, `aba`

Tổng $= 1 + 2 + 2 = 5$ xâu con phân biệt: a, b, ab, ba, aba — đúng (chú ý aa không tồn tại trong aba).

Cài đặt

Phiên bản dưới dùng next dạng mảng cố định 26 ký tự (nhanh nhất cho bảng chữ a–z). Nếu bảng chữ lớn/thưa, đổi sang map<char,int> để tiết kiệm bộ nhớ.

#include <bits/stdc++.h>
using namespace std;

struct SuffixAutomaton {
    static const int A = 26;        // kích thước bảng chữ
    struct State {
        int len, link;
        int next[A];
        long long cnt;              // endpos size (số lần xuất hiện)
        bool is_clone;
    };
    vector<State> st;
    int last;

    SuffixAutomaton(int n = 0) {
        st.reserve(2 * max(n, 1));  // tối đa 2N-1 đỉnh -> cấp phát sẵn
        newState(0, -1, false);     // đỉnh khởi đầu t0
        last = 0;
    }

    int newState(int len, int link, bool clone) {
        State s;
        s.len = len; s.link = link;
        s.cnt = clone ? 0 : 0;      // sẽ gán 1 cho đỉnh "thật" bên dưới
        s.is_clone = clone;
        memset(s.next, -1, sizeof(s.next));
        st.push_back(s);
        return (int)st.size() - 1;
    }

    void extend(int c) {            // c là 0..25
        int cur = newState(st[last].len + 1, -1, false);
        st[cur].cnt = 1;            // mỗi tiền tố đóng góp đúng 1 vị trí kết thúc
        int p = last;
        // nối cạnh c cho mọi hậu tố chưa có cạnh c
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;       // mọi hậu tố đều mới -> link về t0
        } else {
            int q = st[p].next[c];
            if (st[q].len == st[p].len + 1) {
                st[cur].link = q;   // q đã đúng lớp, không cần tách
            } else {
                // tách (clone) q: tạo đỉnh giữ phần xâu ngắn
                int clone = newState(st[p].len + 1, st[q].link, true);
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                // chuyển các cạnh đang trỏ q (với cùng len) sang clone
                while (p != -1 && 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 ch : s) extend(ch - 'a');
    }

    // Tính endpos size cho từng đỉnh: cộng dồn theo cây suffix link,
    // từ đỉnh len LỚN xuống len NHỎ (đây chính là thứ tự topo của cây link).
    void calcCnt() {
        int n = st.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        // counting sort theo len cho O(N)
        sort(order.begin(), order.end(),
             [&](int a, int b){ return st[a].len > st[b].len; });
        for (int v : order)
            if (st[v].link > 0 || (st[v].link == 0 && v != 0))
                if (st[v].link != -1)
                    st[st[v].link].cnt += st[v].cnt;
    }
};

Ứng dụng 1 — Đếm xâu con phân biệt (bài `distsubstr`)

SuffixAutomaton sam(s.size());
sam.build(s);
long long ans = 0;
for (int v = 1; v < (int)sam.st.size(); v++)
    ans += sam.st[v].len - sam.st[sam.st[v].link].len; // mỗi lớp góp len - len(link)
cout << ans << "\n";

Ứng dụng 2 — Đếm số lần xuất hiện của mẫu (bài `cntpat`, `findpat`)

Sau khi calcCnt(), đỉnh đến được khi đi theo các cạnh của mẫu $p$ chính là lớp chứa $p$ ; số lần xuất hiện $= cnt$ của đỉnh đó. Nếu đi giữa chừng không có cạnh ⇒ $p$ không xuất hiện.

sam.calcCnt();
long long countOcc(const string& p) {
    int cur = 0;
    for (char ch : p) {
        int c = ch - 'a';
        if (sam.st[cur].next[c] == -1) return 0; // không tồn tại
        cur = sam.st[cur].next[c];
    }
    return sam.st[cur].cnt;       // findpat chỉ cần kiểm tra >0
}

Ứng dụng 3 — Xâu con chung dài nhất (LCS) của hai xâu

// Xây SAM cho s1, rồi "chạy" s2 trên automaton.
SuffixAutomaton sam(s1.size());
sam.build(s1);
int cur = 0, len = 0, best = 0;
for (char ch : s2) {
    int c = ch - 'a';
    while (cur != 0 && sam.st[cur].next[c] == -1) { // tụt suffix link khi kẹt
        cur = sam.st[cur].link;
        len = sam.st[cur].len;
    }
    if (sam.st[cur].next[c] != -1) { cur = sam.st[cur].next[c]; len++; }
    best = max(best, len);
}

Độ phức tạp

Thời gian xây dựng: $O (N \cdot | Σ |)$ với mảng next cố định, hoặc $O (N \log | Σ |)$ với map. Mỗi lần extend chỉ thực hiện một lượng thao tác bù trừ (amortized) hằng số trên các vòng while: tham số $len (l a s t)$ chỉ tăng tối đa $N$ và mỗi bước nhảy suffix link làm nó giảm, nên tổng số bước nhảy qua toàn bộ quá trình là $O (N)$ .
Số đỉnh / cạnh: $\leq 2 N - 1$ đỉnh, $\leq 3 N - 4$ cạnh ⇒ mọi phép duyệt automaton là $O (N)$ .
Bộ nhớ: $O (N \cdot | Σ |)$ với mảng next (mỗi đỉnh giữ 26 con trỏ — đây là phần tốn nhất), hoặc $O (N)$ với map đổi lấy hằng số lớn hơn. Với $N = 10^{5}$ và mảng 26 int: khoảng $2 \cdot 10^{5} \cdot 26 \cdot 4 \approx 20$ MB — vẫn an toàn.
Truy vấn mẫu độ dài $m$ : $O (m)$ (chỉ đi theo cạnh).

⚠️ Lỗi thường gặp

Quên gán cnt = 1 cho đỉnh thật và cnt = 0 cho clone. Clone không ứng với một vị trí kết thúc mới; nếu lỡ cho nó $1$ , mọi số đếm endpos sẽ sai (lớn hơn thực tế). Chỉ đỉnh cur tạo trực tiếp từ một tiền tố mới được nhận $1$ .
Tính cnt mà chưa sắp theo len giảm dần. Phải cộng dồn từ con lên cha trên cây suffix link, tức xử lý đỉnh len lớn trước. Lặp theo thứ tự đỉnh được tạo ra là sai vì clone có thể được tạo sau con của nó.
Cấp phát thiếu đỉnh. SAM có tới $2 N - 1$ đỉnh; nếu khai báo mảng cố định kích thước $N$ (hay $N + 1$ ) sẽ tràn mảng / lỗi runtime. Luôn cấp 2 * N (cộng vài đỉnh đệm).
Quên memcpy mảng next của q sang clone. Clone phải kế thừa toàn bộ cạnh chuyển tiếp của $q$ ; thiếu bước này automaton mất cạnh và truy vấn trả lời sai.
Tràn số khi đếm. Số xâu con phân biệt có thể tới $(\binom{N + 1}{2}) \approx 5 \cdot 10^{9}$ với $N = 10^{5}$ — vượt int. Phải dùng long long.
Nhầm endpos size với số xâu con. cnt[v] là số vị trí xuất hiện của các xâu trong lớp $v$ , còn $len (v) - len (link (v))$ là số xâu con phân biệt trong lớp. Hai đại lượng khác nhau; dùng nhầm sẽ ra kết quả vô nghĩa.
Quên reset khi xử lý nhiều test. SAM giữ trạng thái trong st và last; sang test mới phải tạo lại đối tượng, đừng build chồng lên xâu cũ.

Biến thể / Mở rộng

Đếm xâu con phân biệt theo độ dài $k$ (bài subdist): với mỗi lớp $v$ , các độ dài từ $len (link (v)) + 1$ đến $len (v)$ mỗi giá trị đóng góp đúng một xâu con phân biệt ⇒ cộng $+ 1$ trên đoạn đó bằng mảng hiệu (difference array).
Xâu con phân biệt nhỏ thứ $k$ theo thứ tự từ điển (bài subord1/subord2): tính $paths (v)$ = số xâu con phân biệt bắt đầu tại $v$ bằng DP trên DAG cạnh, rồi đi tham lam theo cạnh nhỏ nhất. Bài II (đếm cả lặp) chỉ khác ở việc khởi tạo trọng số bằng cnt.
Xâu con lặp lại dài nhất (bài repsubstr): chính là $max {len (v) : cnt (v) \geq 2}$ — lớp xuất hiện ở $\geq 2$ vị trí.
LCS của nhiều xâu, Generalized SAM (xây trên nhiều xâu cùng lúc), và liên hệ với Suffix Array / Suffix Tree: cây suffix link của SAM của $s$ đảo chính là suffix tree của $s$ .

	Suffix Array	Suffix Automaton
Xây dựng	$O (N \log N)$	$O (N \cdot \| Σ \|)$
Bộ nhớ	$O (N)$	$O (N \cdot \| Σ \|)$
Đếm xâu con phân biệt	qua LCP	trực tiếp $\sum (l e n - l e n_{l i n k})$
Đếm số lần xuất hiện mẫu	nhị phân trên SA	$O (m)$ đi cạnh
LCS nhiều xâu	phức tạp	tự nhiên

Bài tập luyện

Tìm Mẫu (findpat) — (Kỳ cựu) Kiểm tra mỗi mẫu có là xâu con hay không — chỉ cần đi theo cạnh SAM, bài nhập môn để làm quen cấu trúc next.
Đếm Mẫu (cntpat) — (Kỳ cựu) Đếm số lần xuất hiện mỗi mẫu: luyện tính endpos size qua cộng dồn trên cây suffix link.
Xâu Con Phân Biệt (distsubstr) — (Chuyên gia) Đếm tổng số xâu con phân biệt bằng công thức $\sum (len - {len}_{link})$ — ứng dụng kinh điển nhất của SAM.
Xâu Con Lặp Lại (repsubstr) — (Chuyên gia) Tìm xâu con lặp dài nhất = $max len (v)$ với $cnt (v) \geq 2$ ; cần truy vết lại xâu từ đỉnh.
Phân Bố Xâu Con (subdist) — (Chuyên gia) Đếm xâu con phân biệt theo từng độ dài $k$ — mở rộng công thức lớp endpos bằng mảng hiệu.
Thứ Tự Xâu Con I (subord1) — (Chuyên gia) Tìm xâu con phân biệt nhỏ thứ $k$ theo từ điển bằng DP đếm đường đi trên DAG của SAM rồi đi tham lam.