Z-functions

Z-function là gì?

Z-function là một kỹ thuật trong xử lý chuỗi (string processing), thường dùng trong các bài toán liên quan đến việc tìm kiếm mẫu con (pattern matching).

Cho một chuỗi S có độ dài n, Z-function là một mảng Z[] cũng có độ dài n, trong đó:

• Z[i] là độ dài phần tiền tố dài nhất bắt đầu từ vị trí i và cũng là tiền tố của chuỗi S.

Hay nói cách khác:
Z[i] = length of the longest substring starting at i which is also a prefix of S.

Ví dụ minh họa

Với chuỗi S = "aabcaabxaaaz", mảng Z-function sẽ là:

Index:      0 1 2 3 4 5 6 7 8 9 10 11
S:          a a b c a a b x a a  a  z
Z-function: 0 1 0 0 3 1 0 0 2 1  1  0

Giải thích:

• Z[1] = 1 vì chuỗi bắt đầu từ S[1] = "a" khớp với tiền tố "a" của S.
• Z[4] = 3 vì "aab" (bắt đầu từ S[4]) khớp với tiền tố "aab".

Ứng dụng của Z-function trong lập trình

a. Tìm tất cả vị trí khớp của một mẫu P trong chuỗi T:

Giải pháp:

• Tạo chuỗi S = P + "#" + T (ký tự # là phân cách không xuất hiện trong cả P và T).
• Tính Z-function của S.
• Mỗi i mà Z[i] == |P| là vị trí khớp của mẫu P trong T.

Ví dụ:
Tìm mẫu abc trong văn bản abcabcabc.

string P = "abc", T = "abcabcabc";
string S = P + "#" + T;
vector<int> Z = computeZ(S);

for (int i = P.size() + 1; i < S.size(); ++i) {
    if (Z[i] == P.size()) {
        cout << "Match at position " << i - P.size() - 1 << endl;
    }
}

b. Lập trình thi đấu – bài toán lặp tiền tố

Z-function thường dùng trong:

• Kiểm tra xem chuỗi có cấu trúc lặp không (ví dụ, chuỗi ababab có thể viết lại thành ab lặp 3 lần).
• Tính toán số lần một mẫu xuất hiện như tiền tố trong nhiều vị trí.
• Các bài toán về border (tiền tố cũng là hậu tố).

Ưu điểm

• Tính Z-function có thể thực hiện trong thời gian O(n).
• Có thể dùng thay thế cho thuật toán KMP phức tạp mà vẫn làm được các bài toán matching hiệu quả.

Tổng kết

Z-function là một kỹ thuật mạnh mẽ và dễ cài đặt trong xử lý chuỗi. Nó đặc biệt hữu ích trong lập trình thi đấu và các bài toán pattern matching, kiểm tra tính lặp, hoặc tiền tố đặc biệt. Nắm vững Z-function giúp bạn xử lý hiệu quả nhiều bài toán chuỗi tưởng như rất phức tạp.