Chương trình C cho thuật toán Rabin-Karp tìm mẫu (Pattern Searching)

Tìm mẫu trong chuỗi (Pattern matching): kiểm tra chuỗi mẫu có xuất hiện trong chuỗi văn bản hay không. Nếu có, hiển thị vị trí.

Input: txt = "HERE IS A NICE CAP", pattern = "NICE"
Output: Pattern found at index 10

Input: txt = "XYZXACAADXYZXYZX", pattern = "XYZX"
Output: Pattern found at index 0, 9, 12

Rabin-Karp là thuật toán tìm mẫu hiệu quả hơn Naive. Cũng trượt cửa sổ từng ký tự, nhưng thay vì so sánh từng ký tự, nó tính giá trị hash. Chỉ khi hash khớp mới so sánh chi tiết từng ký tự. Chỉ 1 so sánh hash cho mỗi đoạn văn bản → hiệu quả hơn.

Thời gian tiền xử lý: O(m)
Độ phức tạp trung bình: O(m+n)
Trường hợp xấu: O(mn)

Thuật toán

rabinkarp(text, pattern, prime):
  pat_len = độ dài pattern
  str_len = độ dài text
  patHash = 0, strHash = 0, h = 1
  maxChar = số ký tự trong bảng chữ cái

  for i = 0 đến pat_len-1:
    h = (h * maxChar) % prime

  for i = 0 đến pat_len-1:
    patHash = (maxChar * patHash + pattern[i]) % prime
    strHash = (maxChar * strHash + text[i]) % prime

  for i = 0 đến str_len - pat_len:
    if patHash == strHash:
      for j = 0 đến pat_len-1:
        if text[i+j] != pattern[j]: break
      if j == pat_len: in "Pattern found at index i"

    if i < str_len - pat_len:
      strHash = (maxChar * (strHash - text[i]*h) + text[i+pat_len]) % prime
      if strHash < 0: strHash += prime

Ví dụ mã nguồn

#include <stdio.h>
#include <string.h>

int main() {
    char txt[80], pat[80];
    int q;

    printf("Nhap chuoi chua (text):\n");
    scanf("%s", txt);
    printf("Nhap mau can tim (pattern):\n");
    scanf("%s", pat);

    int d = 256;  // số ký tự ASCII
    printf("Nhap so nguyen to (prime):\n");
    scanf("%d", &q);

    int M = strlen(pat);
    int N = strlen(txt);
    int i, j, p = 0, t = 0, h = 1;

    for (i = 0; i < M - 1; i++)
        h = (h * d) % q;

    for (i = 0; i < M; i++) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }

    for (i = 0; i <= N - M; i++) {
        if (p == t) {
            for (j = 0; j < M; j++)
                if (txt[i + j] != pat[j]) break;
            if (j == M)
                printf("Pattern found at index %d\n", i);
        }
        if (i < N - M) {
            t = (d * (t - txt[i] * h) + txt[i + M]) % q;
            if (t < 0) t += q;
        }
    }
    return 0;
}

Kết quả đầu ra

Nhap chuoi chua: tutorialspointisthebestprogrammingwebsite
Nhap mau can tim: p
Nhap so nguyen to: 3
Pattern found at index 8
Pattern found at index 21