有限オートマトンの効率的な構築

有限オートマトンを構築することで、テキストのパターン検索を簡単に実行できます。最初に、有限オートマトンの遷移表を作成するために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（pattern、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

patternSearch （テキスト、パターン）

入力- メインテキストとパターン

出力- パターンが見つかったインデックス。

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