Xây dựng hiệu quả dữ liệu tự động hữu hạn

Bằng cách xây dựng Dữ liệu tự động hữu hạn, chúng ta có thể đơn giản thực hiện tìm kiếm mẫu trong văn bản. Đầu tiên, chúng ta phải điền vào một mảng 2D để tạo bảng chuyển tiếp của các ô tự động hữu hạn. Khi bảng được tạo, thủ tục tìm kiếm rất đơn giản. Bằng cách bắt đầu từ trạng thái đầu tiên của automaton, khi chúng ta đạt đến trạng thái cuối cùng, điều đó có nghĩa là mẫu được tìm thấy trong chuỗi.

Đối với cấu trúc ô tô hữu hạn, độ phức tạp về thời gian là O (M * K), M là độ dài mẫu và K là một số ký tự khác nhau. Độ phức tạp của tìm kiếm mẫu chính là O (n).

Đầu vào và Đầu ra

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

Thuật toán

fillTransTable (mẫu, transTable)

Đầu vào - Mẫu và bảng chuyển tiếp để điền vào quá trình chuyển đổi

Đầu ra - Bảng chuyển tiếp đã điền

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 (văn bản, mẫu)

Đầu vào - Văn bản chính và mẫu

Đầu ra - Chỉ mục, nơi các mẫu được tìm thấy.

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

Ví dụ

#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;
   }
}

Đầu ra

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