Thuật toán Aho-Corasick tìm mẫu (Pattern Searching) trong C++

Cho chuỗi đầu vào và mảng từ khóa. Tìm tất cả vị trí xuất hiện của mọi từ khóa trong chuỗi bằng thuật toán Aho-Corasick.

Aho-Corasick là thuật toán tìm kiếm đa mẫu (multi-pattern) mạnh mẽ, dùng cấu trúc Trie (cây tiền tố) kết hợp failure links (suffix links) và output links. Độ phức tạp: O(N + L + Z) với N=độ dài chuỗi, L=tổng độ dài từ khóa, Z=số lần khớp.

Các thành phần chính

• Trie: Cây tiền tố, mỗi cạnh gán 1 ký tự
• Failure Link: Khi không khớp, lùi về trạng thái tiền tố dài nhất vẫn khớp
• Output Link: Chuỗi các từ khóa kết thúc tại nút hiện tại
• FindNextState: Chuyển trạng thái dựa trên ký tự tiếp theo

Các bước xây dựng

1. Xây Trie từ các từ khóa
2. Xây failure links bằng BFS
3. Xây output links (kết hợp từ failure)
4. Duyệt chuỗi đầu vào, dùng FindNextState

Ví dụ mã nguồn

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_STATES = 310;
const int MAX_CHARS = 26;

int out[MAX_STATES];
int fail[MAX_STATES];
int go[MAX_STATES][MAX_CHARS];

int buildMachine(vector<string> &words, char low='a', char high='z') {
    fill(begin(out), end(out), 0);
    fill(begin(fail), end(fail), -1);
    for (auto &row : go) fill(begin(row), end(row), -1);
    
    int states = 1;
    for (int i = 0; i < words.size(); i++) {
        int cur = 0;
        for (char ch : words[i]) {
            int c = ch - low;
            if (go[cur][c] == -1) go[cur][c] = states++;
            cur = go[cur][c];
        }
        out[cur] |= (1 << i);
    }
    for (int c = 0; c < MAX_CHARS; c++)
        if (go[0][c] == -1) go[0][c] = 0;
    
    queue<int> q;
    for (int c = 0; c <= high-low; c++)
        if (go[0][c] != 0) { fail[go[0][c]] = 0; q.push(go[0][c]); }
    
    while (!q.empty()) {
        int state = q.front(); q.pop();
        for (int c = 0; c <= high-low; c++) {
            if (go[state][c] != -1) {
                int f = fail[state];
                while (go[f][c] == -1) f = fail[f];
                f = go[f][c];
                fail[go[state][c]] = f;
                out[go[state][c]] |= out[f];
                q.push(go[state][c]);
            }
        }
    }
    return states;
}

int nextState(int cur, char ch, char low='a') {
    int c = ch - low;
    while (go[cur][c] == -1) cur = fail[cur];
    return go[cur][c];
}

vector<int> searchWords(string text, vector<string> &words, char low='a', char high='z') {
    buildMachine(words, low, high);
    int cur = 0;
    vector<int> res(words.size(), -1);
    for (int i = 0; i < text.size(); i++) {
        cur = nextState(cur, text[i], low);
        if (out[cur] == 0) continue;
        for (int j = 0; j < words.size(); j++)
            if (out[cur] & (1<

Kết quả
Tìm từ khóa trong: Allisheall
Từ 'All' bắt đầu tại 5, kết thúc tại 8
Từ 'she' bắt đầu tại 4, kết thúc tại 7
Từ 'is' bắt đầu tại 1, kết thúc tại 3