Thuật toán Rabin-Karp tìm mẫu

Giới thiệu

Rabin-Karp là thuật toán tìm mẫu hiệu quả hơn. Thay vì kiểm tra từng ký tự cho mọi vị trí, nó tính giá trị hash. Chỉ khi hash trùng khớp mới so sánh chi tiết từng ký tự.

Độ phức tạp: O(m + n) trung bình, O(mn) trường hợp xấu.

Đầ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

rabinKarpSearch(text, pattern, prime)

Đầu vào: Văn bản chính, mẫu, và một số nguyên tố để tính hash

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

Begin
  patLen := độ dài pattern, strLen := độ dài string
  patHash := 0, strHash := 0, h := 1
  maxChar := tổng số ký tự trong tập ký tự
  với chỉ số i của mọi ký tự trong pattern làm:
    h := (h * maxChar) mod prime
  done
  với chỉ số i của mọi ký tự trong pattern làm:
    patHash := (maxChar * patHash + pattern[i]) mod prime
    strHash := (maxChar * strHash + text[i]) mod prime
  done
  với i := 0 đến (strLen - patLen) làm:
    nếu patHash = strHash thì
      với charIndex := 0 đến patLen - 1 làm:
        nếu text[i+charIndex] ≠ pattern[charIndex] thì break
      done
      nếu charIndex = patLen thì in vị trí i
    nếu i < (strLen - patLen) thì
      strHash := (maxChar * (strHash - text[i]*h) + text[i+patLen]) mod prime
      nếu strHash < 0 thì strHash := strHash + prime
  done
End

Ví dụ (C++)

#include <iostream>
#define MAXCHAR 256
using namespace std;

void rabinKarpSearch(string mainString, string pattern, int prime, int array[], int *index) {
  int patLen = pattern.size();
  int strLen = mainString.size();
  int charIndex, pattHash = 0, strHash = 0, h = 1;
  for(int i = 0; i < patLen - 1; i++) {
    h = (h * MAXCHAR) % prime;  // h = d^(M-1) mod prime
  }
  for(int i = 0; i < patLen; i++) {
    pattHash = (MAXCHAR * pattHash + pattern[i]) % prime;
    strHash = (MAXCHAR * strHash + mainString[i]) % prime;
  }
  for(int i = 0; i <= (strLen - patLen); i++) {
    if(pattHash == strHash) {
      for(charIndex = 0; charIndex < patLen; charIndex++) {
        if(mainString[i+charIndex] != pattern[charIndex]) break;
      }
      if(charIndex == patLen) {
        (*index)++;
        array[(*index)] = i;
      }
    }
    if(i < (strLen - patLen)) {
      strHash = (MAXCHAR * (strHash - mainString[i] * h) + mainString[i+patLen]) % prime;
      if(strHash < 0) strHash += prime;
    }
  }
}

int main() {
  string mainString = "ABAAABCDBBABCDDEBCABC";
  string pattern = "ABC";
  int locArray[mainString.size()];
  int prime = 101;
  int index = -1;
  rabinKarpSearch(mainString, pattern, prime, 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