Thuật toán Z (Tìm kiếm mẫu thời gian tuyến tính) trong C++

Thuật toán Z được dùng để tìm vị trí xuất hiện của một mẫu (pattern) trong một chuỗi (string) trong thời gian tuyến tính. Giả sử độ dài chuỗi là n và độ dài mẫu cần tìm là m, độ phức tạp thời gian sẽ là O(m+n).

Thuật toán Z sử dụng mảng Z để tìm vị trí xuất hiện của mẫu.

Mảng Z

Là một mảng có cùng độ dài với chuỗi. Mỗi phần tử của mảng Z chứa độ dài của chuỗi con dài nhất bắt đầu từ vị trí i mà cũng là tiền tố của chính chuỗi đó.

Thuật toán

Cho chuỗi S độ dài n và mẫu P độ dài m.

Chúng ta tạo một mảng Z. Thuật toán lặp qua các ký tự của chuỗi với i = 1 đến n-1. Tạo chuỗi con S[L-R] là chuỗi con tiền tố sao cho 1 ≤ L ≤ i ≤ R.

Với khoảng [L, R] đúng cho i-1 và tất cả giá trị Z đến i-1. Tính Z[i] và khoảng mới [L, R] theo các bước sau:

Bước 1: Nếu i > R, không có chuỗi con tiền tố lớn hơn. Tính khoảng mới bằng cách so sánh S[0] với S[i] (chuỗi từ đầu với chuỗi con từ i). Tìm Z[i] = R - L + 1.
Bước 2: Nếu i ≤ R, [L, R] có thể mở rộng đến i. Với k = i-L, Z[i] ≥ min(Z[k], R-i+1).
  Bước 2.1: Nếu Z[k] < R-i+1, không tồn tại chuỗi con tiền tố dài hơn bắt đầu từ i.
  Bước 2.2: Nếu Z[k] ≥ R-i+1, có thể có chuỗi con dài hơn. Cập nhật [L, R] bằng cách đặt L = i và mở rộng R bằng cách so sánh từ S[R+1].

Quy trình này tìm tất cả giá trị Z trong một lần lặp duy nhất.

Chương trình minh họa

#include <iostream> 
using namespace std; 

void createZarray(string str, int Z[]) { 
    int n = str.length(); 
    int L, R, k; 
    L = R = 0; 
    for (int i = 1; i < n; ++i) { 
        if (i > R) { 
            L = R = i; 
            while (R < n && str[R-L] == str[R]) 
                R++; 
            Z[i] = R-L; 
            R--; 
        } else { 
            k = i-L; 
            if (Z[k] < R-i+1) 
                Z[i] = Z[k]; 
            else { 
                L = i; 
                while (R < n && str[R-L] == str[R]) 
                    R++; 
                Z[i] = R-L; 
                R--; 
            } 
        } 
    } 
} 

void zAlgorithm(string text, string pattern) { 
    string str = pattern + "$" + text; 
    int len = str.length(); 
    int Z[len]; 
    createZarray(str, Z); 
    for (int i = 0; i < len; ++i) { 
        if (Z[i] == pattern.length()) 
            cout << (i - pattern.length() - 1) << "\t"; 
    } 
} 

int main() { 
    string str = "Hello! Welcome To tutorials Point programming tutorial"; 
    string pattern = "tutorial"; 
    cout << "Mẫu '" << pattern << "' tìm thấy trong chuỗi '" << str << "' tại chỉ số \t"; 
    zAlgorithm(str, pattern); 
    return 0; 
}

Kết quả

Mẫu ' tutorial ' tìm thấy trong chuỗi 'Hello! Welcome To tutorials Point programming tutorial ' tại chỉ số 18 46