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