การสร้าง Finite Automata อย่างมีประสิทธิภาพ

โดยการสร้าง Finite Automata เราสามารถทำการค้นหารูปแบบในข้อความได้อย่างง่ายดาย ขั้นแรก เราต้องเติมอาร์เรย์ 2D เพื่อสร้างตารางการเปลี่ยนแปลงของออโตมาตาไฟไนต์ เมื่อสร้างตารางแล้ว ขั้นตอนการค้นหาก็ง่าย โดยเริ่มจากสถานะแรกของหุ่นยนต์ เมื่อเราไปถึงสถานะสุดท้าย หมายความว่าพบรูปแบบในสตริง

สำหรับการสร้างออโตมาตาแบบจำกัด ความซับซ้อนของเวลาคือ 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(รูปแบบ, transTable)

ป้อนข้อมูล - รูปแบบและตารางการเปลี่ยนแปลงเพื่อเติมการเปลี่ยนแปลง

ผลลัพธ์ − ตารางการเปลี่ยนแปลง

Begin
   longPS := 0
   clear all entries of transition table with 0
   transTable[0, patter[0]] = 1      //for the first character of the pattern

   for index of all character i present in pattern, do
      for all possible characters, do
         transTable[i,j] := transTable[longPS, j]
      done

      transTable[i, pattern[i]] := i+1
      if i < pattern size, then
         longPS := transTable[longPS, pattern[i]]
   done
End

ค้นหารูปแบบ (ข้อความ รูปแบบ)

ป้อนข้อมูล - ข้อความหลักและรูปแบบ

ผลลัพธ์ − ดัชนีที่พบรูปแบบ

Begin
   patLen := pattern length
   strLen := string length
   call fillTransTable(pattern, transTable)
   present := 0

   for all character’s index i of text, do
      present := transTable[present, text[i]]
      if present = patLen, then
         print the location (i – patLen +1) as there is the pattern
   done
End

ตัวอย่าง

#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;        // create entries for first state
   }

   transTable[0][pattern[0]] = 1;  //move to first state for first character
   for (int i = 1; i<= pattern.size(); i++) {

      for (int j = 0; j < MAXCHAR ; j++)    // update states using prefix and suffix
         transTable[i][j] = transTable[longPS][j];
      transTable[i][pattern[i]] = i + 1;
      if (i < pattern.size())
         longPS = transTable[longPS][pattern[i]]; //update longest prefix and suffix for next states
   }
}

void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   int transTable[patLen+1][MAXCHAR];     //create transition table for each pattern

   fillTransitionTable(pattern, transTable);
   int presentState = 0;

   for(int i = 0; i<=strLen; i++) {
      presentState = transTable[presentState][mainString[i]];    //move to next state is transition is possible
      if(presentState == patLen) {    //when present state is the final state, pattern found
         (*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