การสร้าง Finite Automata แบบมีประสิทธิภาพสำหรับการค้นหาแพทเทิร์น

บทนำ

การสร้าง Finite Automata ช่วยให้ค้นหาแพทเทิร์นในข้อความได้ง่าย ต้องสร้างตารางสลับสถานะ (Transition Table) เป็นอาร์เรย์ 2 มิติ ก่อน เมื่อสร้างเสร็จ กระบวนการค้นหาจะง่ายมาก เริ่มจากสถานะแรก เมื่อถึงสถานะสุดท้าย หมายถึงพบแพทเทิร์นในสตริง

ความซับซ้อนของเวลา (Time Complexity)

การสร้าง Finite Automata: O(M × K) โดย M คือความยาวแพทเทิร์น, K คือจำนวนตัวอักษรที่แตกต่างกัน
การค้นหาแพทเทิร์นหลัก: O(n)

อินพุตและเอาต์พุต

Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern "ABC"
Output: Pattern found at position: 4
        Pattern found at position: 10
        Pattern found at position: 18

อัลกอริทึม

fillTransTable(pattern, transTable)

Input: แพทเทิร์นและตารางสลับสถานะ
Output: ตารางสลับสถานะที่เติมแล้ว

Begin
    longPS := 0
    ล้างค่าตารางสลับสถานะเป็น 0
    transTable[0, pattern[0]] = 1  // ตัวอักษรแรกของแพทเทิร์น
    for i ทุกดัชนีของตัวอักษรใน pattern do
        for ตัวอักษรที่เป็นไปได้ทั้งหมด do
            transTable[i,j] := transTable[longPS, j]
        done
        transTable[i, pattern[i]] := i+1
        if i < ขนาด pattern then
            longPS := transTable[longPS, pattern[i]]
    done
End

patternSearch(text, pattern)

Input: ข้อความหลักและแพทเทิร์น
Output: ดัชนีที่พบแพทเทิร์น

Begin
    patLen := ความยาว pattern
    strLen := ความยาว string
    เรียก fillTransTable(pattern, transTable)
    present := 0
    for i ทุกดัชนีของตัวอักษรใน text do
        present := transTable[present, text[i]]
        if present = patLen then
            พิมพ์ตำแหน่ง (i - patLen + 1)
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
#define MAXCHAR 256
using namespace std;

void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) {
    int longPS = 0;
    for (int i = 0; i < MAXCHAR; i++) {
        transTable[0][i] = 0;
    }
    transTable[0][pattern[0]] = 1;
    for (int i = 1; i<= pattern.size(); i++) {
        for (int j = 0; j < MAXCHAR; j++)
            transTable[i][j] = transTable[longPS][j];
        transTable[i][pattern[i]] = i + 1;
        if (i < pattern.size())
            longPS = transTable[longPS][pattern[i]];
    }
}

void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();
    int transTable[patLen+1][MAXCHAR];
    fillTransitionTable(pattern, transTable);
    int presentState = 0;
    for(int i = 0; i<=strLen; i++) {
        presentState = transTable[presentState][mainString[i]];
        if(presentState == patLen) {
            (*index)++;
            array[(*index)] = i - patLen + 1;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    FAPatternSearch(mainString, pattern, locArray, &index);
    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i] << endl;
    }
}

ผลลัพธ์

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18