C++ Program: Finite State Automaton (FSA) Based String Search

Finite State Automaton (FSA) String Search สร้าง State Machine จาก Pattern แล้ว Scan Text ใน O(N) Time หลัง Preprocessing O(M × |Σ|) เหมาะสำหรับค้นหา Pattern เดียวใน Text ใหญ่หลายครั้ง

Concept

• State = จำนวนตัวอักษรที่ Match ไปแล้ว (0 ถึง M)
• Transition: State q + Char c → Next State
• Accept State = M (Match เรื่อย)

Transition Table Construction (Efficient O(M|Σ|))

ใช้แนวคิด Longest Prefix Suffix (LPS) เหมือน KMP แต่ Precompute ทุก Transition

โค้ด C++

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

const int ALPHABET_SIZE = 256; // Extended ASCII

// Build Transition Table for Pattern
vector> buildTransitionTable(const string& pattern) {
    int m = pattern.length();
    vector> TF(m + 1);
    
    // State 0: No match yet
    for (int c = 0; c < ALPHABET_SIZE; c++) TF[0][c] = 0;
    TF[0][(unsigned char)pattern[0]] = 1;
    
    // Longest Prefix Suffix for each state
    int lps = 0;
    
    for (int i = 1; i <= m; i++) {
        // Copy transitions from LPS state
        for (int c = 0; c < ALPHABET_SIZE; c++) {
            TF[i][c] = TF[lps][c];
        }
        
        // Update transition for pattern[i] (if not at terminal state)
        if (i < m) {
            TF[i][(unsigned char)pattern[i]] = i + 1;
            // Update LPS for next iteration
            lps = TF[lps][(unsigned char)pattern[i]];
        }
    }
    
    return TF;
}

// Search Pattern in Text using FSA
vector fsaSearch(const string& text, const string& pattern) {
    if (pattern.empty()) return {};
    
    auto TF = buildTransitionTable(pattern);
    int m = pattern.length();
    vector matches;
    
    int state = 0;
    for (int i = 0; i < text.length(); i++) {
        unsigned char c = text[i];
        state = TF[state][c];
        
        if (state == m) {
            matches.push_back(i - m + 1); // Match found at index
        }
    }
    return matches;
}

int main() {
    string text = "AABAA ABBAACCDD CCDDAABAA";
    string pattern = "AABAA";
    
    cout << "Text:    " << text << "\n";
    cout << "Pattern: " << pattern << "\n\n";
    
    auto matches = fsaSearch(text, pattern);
    
    if (matches.empty()) {
        cout << "Pattern not found\n";
    } else {
        cout << "Pattern found at indices: ";
        for (int idx : matches) cout << idx << " ";
        cout << "\n";
        
        // Visualize matches
        for (int idx : matches) {
            cout << "Index " << idx << ": ";
            for (int i = 0; i < idx; i++) cout << " ";
            cout << pattern << "\n";
        }
    }
    
    return 0;
}

ผลลัพธ์

Text:    AABAA ABBAACCDD CCDDAABAA
Pattern: AABAA

Pattern found at indices: 0 20
Index 0:  AABAA
Index 20:                     AABAA

Complexity Analysis

เมื่อเทียบกับ KMP: KMP ใช้ O(M) Space และ O(M+N) Time (ไม่คูณ |Σ|) แต่ FSA เร็วกว่าในการ Search จริงเพราะไม่มี Backtracking

เมื่อไหร่ควรใช้ FSA?

• ค้นหา Pattern เดียวใน Text หลายครั้ง (Preprocess ครั้งเดียว ใช้หลายครั้ง)
• Text Streaming (Process Char by Char)
• Hardware Implementation (FPGA/ASIC)
• Lexical Analyzers, Tokenizers

การขยาย: Multiple Patterns (Aho-Corasick)

สำหรับหลาย Patterns ใช้ Aho-Corasick Algorithm สร้าง Trie + Failure Links ค้นหาได้ใน O(N + Total Pattern Length + Matches)

Unicode Support

สำหรับ UTF-8 ต้อง Decode เป็น Code Points ก่อน หรือใช้ Library เช่น ICU, RE2

C++ Program: Levenshtein Distance (Edit Distance) Algorithm

C++ Program: Repeated String Search (Naive Algorithm)