Aho-Corasick là thuật toán tìm kiếm nhiều pattern trong text đồng thời, trong . Được xây dựng trên Trie với failure links (tương tự KMP).
Ứng dụng: Tìm tất cả vị trí xuất hiện của một tập từ khóa trong văn bản.
Ý tưởng
- Xây dựng Trie từ tập pattern.
- Thêm failure link cho mỗi node: trỏ đến node tương ứng với prefix suffix dài nhất của chuỗi từ gốc đến node đó — giống với failure function trong KMP.
- Khi duyệt text, nếu không khớp, nhảy theo failure link thay vì quay đầu.
Cài đặt
const int MAXN = 1e5 + 5;
const int ALPHA = 26;
struct AhoCorasick {
int next[MAXN][ALPHA], fail[MAXN], cnt;
// cnt[node]: số pattern kết thúc tại node (hoặc qua fail link)
void init() {
cnt = 0;
memset(next[0], -1, sizeof(next[0]));
fail[0] = 0;
}
// Thêm một pattern vào Trie
void insert(const string& s, int id) {
int cur = 0;
for (char c : s) {
int x = c - 'a';
if (next[cur][x] == -1) {
++cnt;
memset(next[cnt], -1, sizeof(next[cnt]));
fail[cnt] = 0;
next[cur][x] = cnt;
}
cur = next[cur][x];
}
// Đánh dấu kết thúc (có thể lưu list pattern ID tại đây)
}
// Xây dựng failure links bằng BFS
void build() {
queue<int> q;
for (int c = 0; c < ALPHA; c++) {
if (next[0][c] == -1) next[0][c] = 0;
else {
fail[next[0][c]] = 0;
q.push(next[0][c]);
}
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < ALPHA; c++) {
if (next[u][c] == -1) {
// Không có cạnh → dùng cạnh từ fail[u]
next[u][c] = next[fail[u]][c];
} else {
fail[next[u][c]] = next[fail[u]][c];
q.push(next[u][c]);
}
}
}
}
// Duyệt text, trả về số lần khớp tại mỗi vị trí
void search(const string& text, vector<int>& match_count) {
int cur = 0;
for (int i = 0; i < (int)text.size(); i++) {
cur = next[cur][text[i] - 'a'];
// Đếm tất cả pattern kết thúc tại cur (theo fail link)
int tmp = cur;
while (tmp) {
match_count[i] += /* số pattern kết thúc tại tmp */ 0;
tmp = fail[tmp];
}
}
}
} ac;
Ví dụ đầy đủ
#include <bits/stdc++.h>
using namespace std;
const int ALPHA = 26;
struct AhoCorasick {
vector<array<int, ALPHA>> go;
vector<int> fail, out; // out[u] = số pattern kết thúc tại u
AhoCorasick() {
go.push_back({});
fill(go[0].begin(), go[0].end(), -1);
fail.push_back(0);
out.push_back(0);
}
void insert(const string& s) {
int cur = 0;
for (char ch : s) {
int c = ch - 'a';
if (go[cur][c] == -1) {
go[cur][c] = go.size();
go.push_back({});
fill(go.back().begin(), go.back().end(), -1);
fail.push_back(0);
out.push_back(0);
}
cur = go[cur][c];
}
out[cur]++;
}
void build() {
queue<int> q;
for (int c = 0; c < ALPHA; c++) {
if (go[0][c] == -1) go[0][c] = 0;
else { fail[go[0][c]] = 0; q.push(go[0][c]); }
}
while (!q.empty()) {
int u = q.front(); q.pop();
out[u] += out[fail[u]]; // gộp số match từ fail link
for (int c = 0; c < ALPHA; c++) {
if (go[u][c] == -1) go[u][c] = go[fail[u]][c];
else { fail[go[u][c]] = go[fail[u]][c]; q.push(go[u][c]); }
}
}
}
// Trả về tổng số lần tất cả pattern xuất hiện trong text
long long search(const string& text) {
long long res = 0;
int cur = 0;
for (char ch : text) {
cur = go[cur][ch - 'a'];
res += out[cur];
}
return res;
}
} ac;
int main() {
int n; cin >> n;
while (n--) {
string p; cin >> p;
ac.insert(p);
}
ac.build();
string text; cin >> text;
cout << ac.search(text) << "\n";
}
Độ phức tạp
| Bước | Độ phức tạp |
|---|---|
| Xây dựng Trie | |
| Xây dựng fail links | |
| Tìm kiếm |
Khi nào dùng Aho-Corasick?
- Cần tìm nhiều pattern trong một text (dùng KMP riêng từng cái sẽ là ).
- Đếm số lần xuất hiện của tập từ khóa.
- Bài DP trên automaton Aho-Corasick (đếm số xâu độ dài chứa ít nhất một pattern).
Bình luận