Thuật toán Apostolico-Crochemore

Đặc điểm chính

Ý tưởng

Bảng biên của KMP cho biết, ứng với mỗi tiền tố x[0..i-1] của mẫu, biên "mạnh" dài nhất. Nếu tiền tố mẫu x[0..ℓ-1] (với ℓ được chọn phù hợp) là luỹ thừa của một chu kỳ ngắn u, thì khi so cửa sổ với văn bản, phần đầu x[0..ℓ-1] thường lặp lại có quy luật — ta không cần so từng ký tự của nó ngay từ đầu mà có thể hoãn lại, so phần thân mẫu (từ vị trí ℓ trở đi) trước, và chỉ quay lại kiểm tra phần đầu khi phần thân đã khớp trọn.

Cách làm này giúp tránh lặp lại các phép so sánh trên đoạn đầu có tính chu kỳ mỗi khi cửa sổ trượt một khoảng ngắn — vốn là điểm yếu của brute-force/Morris-Pratt khi mẫu có cấu trúc lặp ở đầu. Bằng cách trì hoãn và dùng thêm một con trỏ k theo dõi tiến độ khớp của phần đầu, Apostolico-Crochemore đạt cận 3n/2 so sánh, tương đương Colussi nhưng với cách tiếp cận và cấu trúc dữ liệu đơn giản hơn nhiều (không cần các bảng hmax, kmin, rmin).

Mô tả chi tiết

Trước hết tính ℓ: chỉ số nhỏ nhất sao cho x[0..ℓ-1] là tiền tố "chu kỳ" — cụ thể, ℓ là độ dài lớn nhất mà x[i-1] == x[i] liên tiếp kể từ đầu (tức đoạn đầu là luỹ thừa của ký tự x[0]); nếu toàn mẫu chỉ gồm một ký tự lặp lại, xử lý riêng bằng việc đếm loạt ký tự. Đây là định nghĩa đơn giản hoá phổ biến của ℓ; ý nghĩa cốt lõi là x[0..ℓ-1] đủ "đơn giản/lặp" để có thể kiểm tra riêng ở cuối.

Tính bảng kmpNext như trong KMP.

Pha tìm kiếm dùng ba con trỏ:

Với mỗi cửa sổ: so x[i] với y[i+j] tăng dần i chừng nào còn khớp. Nếu i đạt m (thân khớp trọn), kiểm tra thêm phần đầu bằng cách so x[k] với y[j+k] tăng k tới khi đủ ℓ ký tự hoặc lệch; nếu k đạt ℓ thì báo khớp toàn bộ tại j.

Sau đó trượt cửa sổ đi i - kmpNext[i] (như KMP) và cập nhật k:

Nhờ mang giá trị k giữa các lần thử, thuật toán tránh so lại những ký tự của phần đầu đã được xác nhận khớp trước đó.

Cài đặt bằng C

#include <stdio.h>
#include <stdlib.h>

void preKmp(char *x, int m, int kmpNext[]) {
    int i = 0, j = -1;
    kmpNext[0] = -1;
    while (i < m) {
        while (j > -1 && x[i] != x[j]) j = kmpNext[j];
        i++; j++;
        if (i < m && x[i] == x[j]) kmpNext[i] = kmpNext[j];
        else kmpNext[i] = j;
    }
}

void search(char *x, int m, char *y, int n) {
    int i, j, k, ell;
    int *kmpNext;

    /* độ dài phần đầu có tính chu kỳ đơn giản (ở đây: loạt ký tự lặp) */
    for (ell = 1; ell < m && x[ell - 1] == x[ell]; ++ell);

    if (ell == m) {                 /* mẫu là a^m: đếm loạt trực tiếp */
        k = 0;
        for (j = 0; j < n; ++j) {
            if (y[j] == x[0]) { ++k; if (k >= m) printf("Tim thay tai vi tri %d\n", j - m + 1); }
            else k = 0;
        }
        return;
    }

    kmpNext = (int *) malloc((m + 1) * sizeof(int));
    preKmp(x, m, kmpNext);

    i = ell; j = k = 0;
    while (j + m <= n) {
        while (i < m && x[i] == y[i + j]) ++i;
        if (i >= m) {
            while (k < ell && x[k] == y[j + k]) ++k;
            if (k >= ell) printf("Tim thay tai vi tri %d\n", j);
        }
        j += i - kmpNext[i];
        if (i == ell)
            k = (k - 1 > 0) ? k - 1 : 0;
        else if (kmpNext[i] <= ell) {
            k = (kmpNext[i] > 0) ? kmpNext[i] : 0;
            i = ell;
        } else {
            k = ell;
            i = kmpNext[i];
        }
    }
    free(kmpNext);
}

Ví dụ minh họa

Xét x = "GCAGAGAG" (m = 8) trên y = "GCATCGCAGAGAGTATACAGTACG" (n = 24).

Vì x[0]=G khác ngay x[1]=C, phần đầu không có loạt lặp thật sự dài: ℓ = 1. Con trỏ thân i bắt đầu từ 1.

Bảng kmpNext (như ở bài KMP): -1 0 0 -1 1 -1 1 -1 1.

Vài lần thử đầu (con trỏ j là vị trí cửa sổ, i bắt đầu lại từ ℓ = 1):

Việc trì hoãn kiểm tra ký tự đầu x[0] cho tới khi phần thân đã khớp trọn giúp thuật toán tiết kiệm so sánh trong các lần thử thất bại sớm.

Tài liệu tham khảo