Thuật toán Finite Automata tìm mẫu (Pattern Searching) C++

Finite Automata (FA) – Xây dựng máy trạng thái hữu hạn từ pattern, sau đó quét text trong O(n).

• Tiền xử lý O(m × |Σ|), tìm kiếm O(n).
• Phù hợp khi tìm nhiều lần cùng pattern.

Chương trình C++

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

const int ALPHABET = 256;

vector> buildFA(const string& pat) {
    int m = pat.size();
    vector> FA(m+1);
    for (int state = 0; state <= m; state++) {
        for (int ch = 0; ch < ALPHABET; ch++) {
            if (state < m && ch == pat[state]) {
                FA[state][ch] = state + 1;
            } else {
                // Tìm tiền tố dài nhất của pat[0..state-1] + ch là hậu tố của pat[0..state]
                int ns = state;
                while (ns > 0) {
                    if (pat[ns-1] == ch) {
                        bool ok = true;
                        for (int i = 0; i < ns-1; i++)
                            if (pat[i] != pat[state-ns+1+i]) { ok = false; break; }
                        if (ok) break;
                    }
                    ns--;
                }
                FA[state][ch] = ns;
            }
        }
    }
    return FA;
}

void searchFA(const string& txt, const string& pat) {
    auto FA = buildFA(pat);
    int state = 0;
    for (int i = 0; i < (int)txt.size(); i++) {
        state = FA[state][(unsigned char)txt[i]];
        if (state == (int)pat.size())
            cout << "Pattern found at index " << (i - pat.size() + 1) << "\n";
    }
}

int main() {
    string txt = "AABCDAABBDCAABADAABDABAABA";
    string pat = "AABA";
    searchFA(txt, pat);
    return 0;
}

Kết quả

Pattern found at index 11
Pattern found at index 22