Wiki › Thuật toán › Thuật toán xâu › Aho-Corasick

Aho-Corasick

huunguyen Updated Tháng sáu 2, 2026

Aho-Corasick là thuật toán tìm kiếm nhiều mẫu (pattern) cùng lúc trong một văn bản (text). Cho tập $k$ mẫu với tổng độ dài $m = \sum | p_{i} |$ và văn bản độ dài $n$ , thuật toán tìm mọi lần xuất hiện của mọi mẫu trong $O (n + m + z)$ , với $z$ là tổng số lần khớp. So với việc chạy KMP riêng cho từng mẫu mất $O (k \cdot n + m)$ (chậm khi $k$ lớn), Aho-Corasick chỉ quét văn bản đúng một lần.

Ý tưởng cốt lõi: dựng một Trie (cây tiền tố) chứa tất cả các mẫu, rồi gắn thêm liên kết hụt (fail link) — bản tổng quát của hàm hụt trong KMP — để khi đang đọc văn bản mà gặp ký tự không khớp, ta nhảy sang trạng thái tương ứng với hậu tố dài nhất vẫn còn là tiền tố của một mẫu nào đó, thay vì quay lại từ đầu.

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

Hãy tưởng tượng ta đang quét văn bản từ trái sang phải và muốn biết: "hậu tố dài nhất của phần văn bản đã đọc, mà đồng thời là tiền tố của một mẫu nào đó, là gì?". Trạng thái này chính là một node trên Trie của tập mẫu.

Trie gom mọi mẫu lại: đi từ gốc theo các ký tự của một xâu, ta dừng tại node đại diện cho xâu đó. Nếu hai mẫu có chung tiền tố, chúng dùng chung đoạn đầu của Trie — đây là lý do ta xử lý đồng thời được nhiều mẫu mà không lặp lại công.
Fail link của node $u$ (đại diện xâu $S$ ) trỏ tới node đại diện hậu tố thực sự dài nhất của $S$ mà cũng là một tiền tố (node) trong Trie. Đây đúng là ý tưởng hàm hụt KMP, nhưng tính trên cả một cây thay vì một xâu. Khi đang ở $u$ và đọc ký tự $c$ mà $u$ không có cạnh $c$ , ta lùi theo fail link cho tới khi tìm được node có cạnh $c$ (hoặc về gốc). Vì fail link luôn trỏ tới xâu ngắn hơn hẳn, quá trình lùi chắc chắn dừng.
Vì sao đúng? Khi đang ở node $u$ sau khi đọc xong vị trí $i$ của văn bản, $u$ biểu diễn hậu tố-khớp dài nhất kết thúc tại $i$ . Một mẫu $p$ kết thúc tại $i$ khi và chỉ khi $p$ là hậu tố của xâu mà $u$ đại diện — tức node-kết-thúc của $p$ nằm trên chuỗi fail link đi từ $u$ về gốc. Vì vậy, mọi mẫu khớp tại vị trí $i$ được liệt kê bằng cách đi theo các fail link từ $u$ . Chuỗi các node "kết thúc mẫu" trên đường fail link này gọi là dictionary/output link.
Mẹo tăng tốc — automaton đầy đủ (goto function): thay vì lúc chạy mới lùi fail link để tìm cạnh, ta tính sẵn go[u][c]: nếu $u$ có cạnh thật theo $c$ thì giữ nguyên, ngược lại go[u][c] = go[fail[u]][c]. Sau bước dựng (BFS), mỗi bước đọc văn bản chỉ là một phép tra bảng $O (1)$ , biến Trie thành một ô-tô-mát hữu hạn (finite automaton).

Ví dụ chạy tay

Tập mẫu: {"a", "ab", "bab", "bc", "bca", "c", "caa"} (chữ thường). Trước hết dựng Trie (đánh số node theo thứ tự thêm), mỗi node đánh dấu * nếu là nơi kết thúc một mẫu:

            (0) gốc
          a/    b\     c\
        (1)*a   (4)b   (8)*c
        b/        a\      a\
      (2)*ab     (5)bab*  (9)caa? -> (9)c-a (10)*caa
                  ...

Để rõ ràng, liệt kê các node và xâu chúng đại diện:

node : xâu     : kết thúc mẫu?
 0   : ""      :
 1   : "a"     : * (mẫu "a")
 2   : "ab"    : * (mẫu "ab")
 3   : "b"     :
 4   : "ba"    :
 5   : "bab"   : * (mẫu "bab")
 6   : "bc"    : * (mẫu "bc")
 7   : "bca"   : * (mẫu "bca")
 8   : "c"     : * (mẫu "c")
 9   : "ca"    :
10   : "caa"   : * (mẫu "caa")

Tính fail link bằng BFS theo độ sâu (fail của node độ sâu 1 đều về gốc 0). Với node $u$ có cha $p$ qua ký tự $c$ : fail[u] = go[fail[p]][c]. Vài giá trị quan trọng:

node u : xâu   : fail[u] -> xâu          : giải thích (hậu tố dài nhất là 1 tiền tố)
 4 "ba"        : 1 "a"                    : hậu tố "a" là tiền tố mẫu
 5 "bab"       : 2 "ab"                   : hậu tô "ab"
 6 "bc"        : 8 "c"                    : hậu tố "c"
 7 "bca"       : 9 "ca"                   : hậu tố "ca"
 9 "ca"        : 1 "a"                    : hậu tố "a"
10 "caa"       : 1 "a"                    : hậu tố "a"

Chú ý node 7 "bca" có fail tới 9 "ca"; mà bản thân 7 là mẫu, và đi tiếp fail từ 9 -> 1 "a" (cũng là mẫu). Vậy khi automaton đứng ở node 7, các mẫu kết thúc tại đó là: "bca" (chính nó) và "a" (qua chuỗi fail). Ta gộp sẵn số đếm này bằng out[u] += out[fail[u]] trong BFS.

Bây giờ quét văn bản $T =$ bcaa. Bắt đầu ở node 0:

i  ký tự  node hiện tại   out(số mẫu KT tại đây, đã gộp fail)   mẫu khớp kết thúc tại i
-  -----  -------------   ----------------------------------   -----------------------
0   b      0 -go[0][b]-> 3   out[3]=0                            (không)
1   c      3 -go[3][c]-> 6   out[6]=1  ("bc","c"? -> "bc" và    "bc", "c"
                              fail 6->8 "c" cũng là mẫu => 2)
2   a      6 -go[6][a]-> 7   out[7]= "bca"+"a" = 2               "bca", "a"
3   a      7 -go[7][a]-> ?   go[7][a]: 7 không có cạnh 'a',      "caa", "a"
                              go[fail[7]=9][a]=10 "caa";
                              out[10]= "caa"+"a" = 2

Tổng số lần xuất hiện của tất cả mẫu trong bcaa $= 0 + 2 + 2 + 2 = 6$ . Kiểm tra tay: bc(1), c(1), bca(1), a(2 lần — vị trí 2 và 3), caa(1) → đúng 6. Điểm mấu chốt: tại bước $i = 3$ ta không có cạnh thật từ node 7 theo a, automaton tự "lùi" qua bảng go đã dựng sẵn để tới node 10 trong $O (1)$ .

Cài đặt

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

const int ALPHA = 26;

struct AhoCorasick {
    vector<array<int, ALPHA>> go;  // go[u][c]: chuyển trạng thái khi ở u đọc ký tự c
    vector<int> fail, out;         // out[u]: số mẫu kết thúc tại u (đã gộp theo fail)

    AhoCorasick() {
        newNode();                 // node 0 = gốc
    }

    int newNode() {
        go.push_back({});
        fill(go.back().begin(), go.back().end(), -1);
        fail.push_back(0);
        out.push_back(0);
        return (int)go.size() - 1;
    }

    // Thêm một mẫu vào Trie. Trả về node kết thúc (hữu ích nếu cần map mẫu -> node)
    int insert(const string& s) {
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (go[cur][c] == -1) go[cur][c] = newNode();
            cur = go[cur][c];
        }
        out[cur]++;                // một mẫu nữa kết thúc tại node này
        return cur;
    }

    // Dựng fail link + biến Trie thành automaton đầy đủ bằng BFS theo độ sâu
    void build() {
        queue<int> q;
        for (int c = 0; c < ALPHA; c++) {
            if (go[0][c] == -1) go[0][c] = 0;          // cạnh khuyết ở gốc -> về gốc
            else { fail[go[0][c]] = 0; q.push(go[0][c]); }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            // Gộp số mẫu từ node fail: mọi mẫu là hậu tố của xâu(u) đều khớp khi ở u
            out[u] += out[fail[u]];
            for (int c = 0; c < ALPHA; c++) {
                if (go[u][c] == -1) {
                    // Cạnh khuyết: dùng đúng cạnh của fail[u] -> automaton hoá
                    go[u][c] = go[fail[u]][c];
                } else {
                    // Cạnh thật: fail của con = go[fail[u]][c]
                    fail[go[u][c]] = go[fail[u]][c];
                    q.push(go[u][c]);
                }
            }
        }
    }

    // Tổng số lần xuất hiện của TẤT CẢ mẫu trong text
    long long countMatches(const string& text) {
        long long res = 0;
        int cur = 0;
        for (char ch : text) {
            cur = go[cur][ch - 'a'];   // O(1) nhờ bảng go đã dựng
            res += out[cur];           // out đã gộp theo fail -> không cần lùi thủ công
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    string text; 
    cin >> text >> n;
    AhoCorasick ac;
    while (n--) { string p; cin >> p; ac.insert(p); }
    ac.build();
    cout << ac.countMatches(text) << "\n";
}

Khi cần liệt kê mẫu nào khớp (không chỉ đếm): không gộp out mà giữ một vector<int> các id mẫu tại mỗi node, đồng thời thêm link[u] = node "kết thúc mẫu" gần nhất trên chuỗi fail (dictionary link). Tại mỗi vị trí, đi theo link để liệt kê — tổng chi phí $O (z)$ với $z$ là số lần khớp.

Độ phức tạp

Bước	Thời gian	Lý giải
Dựng Trie	$O (m \cdot Σ)$ hoặc $O (m)$	$m = \sum \| p_{i} \|$ node; mỗi node khởi tạo $Σ$ ô của mảng `go`. Dùng `unordered_map` thay mảng thì còn $O (m)$ thời gian nhưng tra cứu chậm hơn.
Dựng fail / automaton	$O (m \cdot Σ)$	BFS qua $m$ node, mỗi node duyệt $Σ$ ký tự để điền `go` và `fail`.
Quét văn bản (chỉ đếm tổng)	$O (n)$	Mỗi ký tự là một phép tra `go` $O (1)$ ; `out` gộp sẵn nên không lùi fail.
Quét + liệt kê mọi vị trí	$O (n + z)$	Thêm $z$ = tổng số lần khớp khi đi theo dictionary link.

Bộ nhớ: $O (m \cdot Σ)$ cho mảng go (bảng chuyển trạng thái) cộng $O (m)$ cho fail, out. Với $Σ = 26$ và $m \leq 5 \times 10^{5}$ , đó là khoảng $5 \times 10^{5} \times 26$ số nguyên $\approx 50$ MB — cần để ý giới hạn bộ nhớ; nếu chật, dùng unordered_map<char,int> cho cạnh để giảm còn $O (m)$ bộ nhớ.

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

Tràn số khi đếm: tổng số lần xuất hiện có thể tới $O (n \cdot k)$ , vượt int dễ dàng (ví dụ văn bản aaaa... và mẫu a, aa, ...). Luôn dùng long long cho biến cộng dồn kết quả.
Quên gộp out[u] += out[fail[u]]: nếu chỉ đếm tại đúng node kết thúc, bạn sẽ bỏ sót các mẫu là hậu tố (ví dụ ở node "bca" quên đếm mẫu "a"). Hoặc phải lùi fail link thủ công mỗi bước — nhưng vòng while(tmp) tmp=fail[tmp] đó có thể là $O (n \sqrt{m})$ hoặc tệ hơn trong trường hợp xấu (chuỗi mẫu a,aa,aaa,...), làm TLE. Gộp out trong BFS là cách an toàn để giữ quét $O (n)$ .
Thứ tự BFS sai khi dựng fail: phải xử lý node theo thứ tự độ sâu tăng dần (BFS), vì fail[u] luôn ở độ sâu nhỏ hơn và phải được tính xong trước. Dùng DFS hay duyệt theo id sẽ cho fail link sai.
Cạnh khuyết ở gốc: ở node 0, mọi go[0][c] khuyết phải trỏ về 0 (không phải $- 1$ ). Quên bước này làm go[fail[u]][c] đọc nhầm $- 1$ và automaton hỏng ngay từ ký tự đầu không khớp.
Reset không sạch giữa các test: nếu giải nhiều test trong một lần chạy, đừng tái dùng các vector cũ mà không clear. Tốt nhất tạo lại đối tượng AhoCorasick (cấp phát động) hoặc reset toàn bộ go/fail/out.
Nhầm "vị trí kết thúc" với "vị trí bắt đầu": automaton báo mẫu kết thúc tại $i$ . Muốn vị trí bắt đầu (1-indexed) của mẫu độ dài $L$ thì lấy $i - L + 2$ . Sai chỗ này gây off-by-one ở các bài hỏi vị trí (vd patpos).

Biến thể / Mở rộng

DP trên automaton: đếm số xâu độ dài $N$ không chứa (hoặc chứa) mẫu nào — đặt trạng thái DP là (vị trí, node automaton), chuyển trạng thái qua go, loại các node "nguy hiểm" (out>0). Đây là ứng dụng mạnh nhất của Aho-Corasick trong combinatorics.
Tìm/đếm vị trí đầu tiên mỗi mẫu: ánh xạ mỗi mẫu tới node kết thúc; khi quét, lan kết quả theo dictionary link để gán vị trí cho mọi mẫu là hậu tố.
Kiểm duyệt với ngăn xếp (stack): xử lý xoá mẫu khi đang ghép văn bản — đẩy ký tự cùng node automaton vào stack, khi out>0 thì pop bỏ đoạn vừa khớp rồi tiếp tục từ node ở đỉnh stack (xem bài censorgo).
Liên hệ: nếu chỉ có một mẫu, Aho-Corasick suy biến thành KMP; phần Trie liên quan tới trang Trie.

Bài tập luyện

Tìm Mẫu (findpat) — (Kỳ cựu) Với mỗi mẫu in YES/NO xem có là xâu con của văn bản không; $k$ lớn ép phải khớp đa mẫu một lượt thay vì KMP từng mẫu — bài nhập môn Aho-Corasick.
Vị Trí Mẫu (patpos) — (Kỳ cựu) Tìm vị trí xuất hiện đầu tiên (1-indexed) của mỗi mẫu; luyện cách lan kết quả theo dictionary link và xử lý chuyển từ "vị trí kết thúc" sang "vị trí bắt đầu".
Đếm Mẫu (cntpat) — (Kỳ cựu) Đếm số lần xuất hiện của từng mẫu trong văn bản; bài đếm kinh điển, cần gộp out theo fail và cộng dồn qua automaton cho từng node-kết-thúc.
Kiểm duyệt (Gold) (censorgo) — (Kỳ cựu) Lặp lại việc xoá mẫu khớp sớm nhất khỏi văn bản; kết hợp Aho-Corasick với ngăn xếp để xử lý các mẫu mới sinh ra sau khi xoá — bài nâng cao đúng tag aho_corasick.