โปรแกรม C++ อัลกอริทึม Finite Automata สำหรับ Pattern Searching

ใช้ Finite Automata Algorithm ค้นหา Pattern ใน Text

ได้รับ text[0..n-1] และ pattern[0..m-1] หาตำแหน่งทั้งหมดที่ pattern ปรากฏใน text

วิธี: Preprocess pattern สร้างตาราง 2D (Transition Function) แล้วสแกน text ตาม state machine

ตัวอย่างโค้ด

#include<stdio.h>
#include<string.h>
#define total_chars 256

int calc_nextstate(char *pat, int M, int state, int x) {
    if (state < M && x == pat[state]) return state+1;
    int ns, i;
    for (ns = state; ns > 0; ns--) {
        if (pat[ns-1] == x) {
            for (i = 0; i < ns-1; i++)
                if (pat[i] != pat[state-ns+1+i]) break;
            if (i == ns-1) return ns;
        }
    }
    return 0;
}

void calc_TF(char *pat, int M, int TF[][total_chars]) {
    for (int state = 0; state <= M; ++state)
        for (int x = 0; x < total_chars; ++x)
            TF[state][x] = calc_nextstate(pat, M, state, x);
}

void calc_occur(char *pat, char *txt) {
    int M = strlen(pat), N = strlen(txt);
    int TF[M+1][total_chars];
    calc_TF(pat, M, TF);
    int state = 0;
    for (int i = 0; i < N; i++) {
        state = TF[state][txt[i]];
        if (state == M) printf("\n Given pattern is found at the index %d", i-M+1);
    }
}

int main() {
    char *txt = "AABCDAABBDCAABADAABDABAABA";
    char *pat = "AABA";
    calc_occur(pat, txt);
    return 0;
}

ผลลัพธ์

Given pattern is found at the index 11
Given pattern is found at the index 22