Tìm kiếm dựa trên Automation Hữu hạn (Finite Automaton) trong C++

Tìm kiếm mẫu (pattern matching) bằng Finite Automaton (FA) tiền xử lý mẫu để xây dựng bảng chuyển trạng thái (transition table), sau đó quét văn bản trong O(n) thời gian — nhanh hơn KMP khi alphabet nhỏ và nhiều lần tìm kiếm cùng mẫu.

Ý tưởng

• Xây dựng DFA (Deterministic Finite Automaton) nhận diện mẫu P[0..m-1].
• Trạng thái q = độ dài tiền tố khớp nhất của P là suffix của văn bản đã đọc.
• Bảng chuyển trạng thái TF[q][ch] = trạng thái tiếp theo khi đọc ký tự ch ở trạng thái q.
• Trạng thái chấp nhận: q == m (tìm thấy mẫu).

Xây dựng bảng chuyển trạng thái (O(m * |Σ|))

void buildTF(const string& pat, vector>& TF) {
    int m = pat.size();
    TF.assign(m + 1, array{});
    
    // Trạng thái 0
    for (int ch = 0; ch < 256; ++ch) TF[0][ch] = 0;
    TF[0][(unsigned char)pat[0]] = 1;
    
    int lps = 0; // Longest Prefix Suffix
    for (int i = 1; i <= m; ++i) {
        // Copy từ trạng thái lps
        for (int ch = 0; ch < 256; ++ch) TF[i][ch] = TF[lps][ch];
        // Cập nhật cho ký tự pat[i]
        if (i < m) TF[i][(unsigned char)pat[i]] = i + 1;
        // Cập nhật lps cho lần sau
        if (i < m) lps = TF[lps][(unsigned char)pat[i]];
    }
}

Tìm kiếm (O(n))

void searchFA(const string& text, const string& pat, const vector>& TF) {
    int state = 0;
    for (int i = 0; i < text.size(); ++i) {
        state = TF[state][(unsigned char)text[i]];
        if (state == pat.size()) {
            cout << "Tim thay tai vi tri: " << (i - pat.size() + 1) << '\n';
        }
    }
}

Chương trình hoàn chỉnh

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

const int ALPHA = 256; // ASCII mở rộng

void buildTransitionTable(const string& pat, vector>& TF) {
    int m = pat.size();
    TF.assign(m + 1, array{});
    
    // State 0
    TF[0].fill(0);
    TF[0][(unsigned char)pat[0]] = 1;
    
    int lps = 0;
    for (int i = 1; i <= m; ++i) {
        // Copy từ lps
        for (int ch = 0; ch < ALPHA; ++ch) TF[i][ch] = TF[lps][ch];
        // Cập nhật ký tự hiện tại
        if (i < m) TF[i][(unsigned char)pat[i]] = i + 1;
        // Cập nhật lps
        if (i < m) lps = TF[lps][(unsigned char)pat[i]];
    }
}

void finiteAutomatonSearch(const string& text, const string& pat) {
    vector> TF;
    buildTransitionTable(pat, TF);
    
    int state = 0;
    for (int i = 0; i < text.size(); ++i) {
        state = TF[state][(unsigned char)text[i]];
        if (state == pat.size()) {
            cout << "Pattern found at index: " << (i - pat.size() + 1) << '\n';
        }
    }
}

int main() {
    string text = "AABAA ABBAACCDD CCDDAABAA";
    string pattern = "AABAA";
    
    cout << "Text: " << text << '\n';
    cout << "Pattern: " << pattern << '\n';
    finiteAutomatonSearch(text, pattern);
    return 0;
}

Kết quả

Text: AABAA ABBAACCDD CCDDAABAA
Pattern: AABAA
Pattern found at index: 0
Pattern found at index: 20

So sánh các thuật toán tìm mẫu

Khi nào dùng FA?

• Alphabet nhỏ (DNA: 4, ASCII: 128/256).
• Tìm kiếm cùng pattern nhiều lần trên nhiều text khác nhau (bảng TF tái sử dụng).
• Yêu cầu thời gian tìm kiếm worst-case O(n) đảm bảo.

FA-based search là kỹ thuật nền tảng của các regex engine (NFA/DFA) và lexical analyzer (lexer/flex).