Xây dựng Tự động Hữu hạn hiệu quả (Finite Automata) tìm mẫu

Giới thiệu

Xây dựng tự động hữu hạn (Finite Automata) cho phép tìm mẫu đơn giản. Điền bảng chuyển trạng thái 2D, sau đó tìm kiếm: bắt đầu từ trạng thái đầu, khi đạt trạng thái cuối nghĩa là tìm thấy mẫu.

Độ phức tạp xây bảng: O(M*K), M độ dài mẫu, K số ký tự khác nhau. Tìm kiếm: O(n).

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

Đầu vào: Văn bản: "ABAAABCDBBABCDDEBCABC", Mẫu: "ABC"
Đầu ra: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

Thuật toán

fillTransTable(pattern, transTable)

Đầu vào: Mẫu và bảng chuyển trạng thái

Đầu ra: Bảng chuyển trạng thái đã điền

Begin
  longPS := 0
  xóa tất cả entries của transTable với 0
  transTable[0, pattern[0]] = 1  // ký tự đầu tiên
  với chỉ số i của mọi ký tự trong pattern làm:
    với mọi ký tự khả thi làm:
      transTable[i,j] := transTable[longPS, j]
    done
    transTable[i, pattern[i]] := i+1
    nếu i < kích thước pattern thì
      longPS := transTable[longPS, pattern[i]]
  done
End

patternSearch(text, pattern)

Đầu vào: Văn bản và mẫu

Đầu ra: Chỉ số tìm thấy mẫu

Begin
  patLen := độ dài pattern, strLen := độ dài string
  gọi fillTransTable(pattern, transTable)
  present := 0
  với chỉ số i của mọi ký tự text làm:
    present := transTable[present, text[i]]
    nếu present = patLen thì in vị trí (i - patLen + 1)
  done
End

Ví dụ (C++)

#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;
  transTable[0][pattern[0]] = 1;
  for (int i = 1; i <= pattern.size(); i++) {
    for (int j = 0; j < MAXCHAR; j++)
      transTable[i][j] = transTable[longPS][j];
    transTable[i][pattern[i]] = i + 1;
    if (i < pattern.size())
      longPS = transTable[longPS][pattern[i]];
  }
}

void FAPatternSearch(string mainString, string pattern, int array[], int *index) {
  int patLen = pattern.size();
  int strLen = mainString.size();
  int transTable[patLen+1][MAXCHAR];
  fillTransitionTable(pattern, transTable);
  int presentState = 0;
  for(int i = 0; i <= strLen; i++) {
    presentState = transTable[presentState][mainString[i]];
    if(presentState == patLen) {
      (*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;
  }
}

Kết quả đầu ra

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