Thuật toán Knuth-Morris-Pratt (KMP)

Giới thiệu

Knuth-Morris-Pratt (KMP) duyệt ký tự từ trái sang phải. Khi mẫu có tiền tố trùng hậu tố, thuật toán tận dụng tính chất này để bỏ qua các so sánh thừa, cải thiện độ phức tạp ngay cả trường hợp xấu.

Độ phức tạp: O(n).

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

Đầu vào: Văn bản: "AAAABAAAAABBBAAAAB", Mẫu: "AAAB"
Đầu ra: Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14

Thuật toán

findPrefix(pattern, m, prefArray)

Đầu vào: Mẫu, độ dài mẫu, mảng lưu vị trí tiền tố

Đầu ra: Mảng tiền tố (prefix array / failure function)

Begin
  length := 0
  prefArray[0] := 0
  với chỉ số i của mọi ký tự trong pattern làm:
    nếu pattern[i] = pattern[length] thì
      tăng length 1
      prefArray[i] := length
    ngược lại
      nếu length ≠ 0 thì
        length := prefArray[length - 1]
        giảm i 1
      ngược lại prefArray[i] := 0
  done
End

kmpAlgorithm(text, pattern)

Đầu vào: Văn bản chính và mẫu cần tìm

Đầu ra: Vị trí tìm thấy mẫu

Begin
  n := kích thước text, m := kích thước pattern
  gọi findPrefix(pattern, m, prefArray)
  trong khi i < n làm:
    nếu text[i] = pattern[j] thì tăng i, j 1
    nếu j = m thì
      in vị trí (i-j)
      j := prefArray[j-1]
    ngược lại nếu i < n VÀ pattern[j] ≠ text[i] thì
      nếu j ≠ 0 thì j := prefArray[j-1]
      ngược lại tăng i 1
  done
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void findPrefix(string pattern, int m, int prefArray[]) {
  int length = 0;
  prefArray[0] = 0;
  for(int i = 1; i < m; i++) {
    if(pattern[i] == pattern[length]) {
      length++;
      prefArray[i] = length;
    } else {
      if(length != 0) {
        length = prefArray[length - 1];
        i--;
      } else prefArray[i] = 0;
    }
  }
}

void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) {
  int n, m, i = 0, j = 0;
  n = mainString.size();
  m = pattern.size();
  int prefixArray[m];
  findPrefix(pattern, m, prefixArray);
  loc = 0;
  while(i < n) {
    if(mainString[i] == pattern[j]) { i++; j++; }
    if(j == m) {
      locArray[loc] = i - j;
      loc++;
      j = prefixArray[j-1];
    } else if(i < n && pattern[j] != mainString[i]) {
      if(j != 0) j = prefixArray[j-1];
      else i++;
    }
  }
}

int main() {
  string str = "AAAABAAAAABBBAAAAB";
  string patt = "AAAB";
  int locationArray[str.size()];
  int index;
  kmpPattSearch(str, patt, locationArray, index);
  for(int i = 0; i < index; i++) {
    cout << "Pattern found at location: " << locationArray[i] << endl;
  }
}

Kết quả đầu ra

Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14