Z-function: z-array và ứng dụng

TL;DR: Z-function tính mảng z[i]: độ dài đoạn bắt đầu tại i trùng khớp với tiền tố của chuỗi. Thuật toán O(n) dùng z-box [l, r) (đoạn S[l..r-1] xa nhất bên phải đã biết là trùng với tiền tố) để tái dùng kết quả đã tính: nếu i nằm trong box hiện tại, lấy z[i-l] làm điểm khởi đầu thay vì so từ đầu. Ứng dụng nổi bật: ghép P + '#' + T rồi tìm vị trí z[i] = |P| để phát hiện mọi lần khớp trong O(n+m). Z-function và failure function của KMP là hai mặt của cùng một ý tưởng về tiền tố, và có thể chuyển đổi cho nhau.

Ở bài trước bạn thấy Rabin-Karp dùng rolling hash để bỏ qua so sánh ký tự. Bài này quay lại hướng "tận dụng tiền tố" như KMP, nhưng thay vì hỏi "hậu tố nào trùng tiền tố?" (lps), Z-function hỏi trực tiếp hơn: "đứng tại vị trí i, đoạn dài bao nhiêu bắt đầu từ đây trùng khớp với phần đầu chuỗi?"

1. Định nghĩa z-array

Hình dung bạn đặt phần đầu chuỗi lên như một cái thước rồi trượt dọc chuỗi: tại mỗi ô, thước khớp được bao nhiêu ký tự liên tiếp thì đó là z.

Cho chuỗi S độ dài n. Z-array là mảng z[0..n-1] với:

z[i] = độ dài của đoạn chung dài nhất giữa S (tính từ đầu) và S[i..] (hậu tố bắt đầu tại i).

Nói cách khác: z[i] là số ký tự lớn nhất sao cho S[0..z[i]-1] = S[i..i+z[i]-1].

Quy ước: z[0] thường bỏ qua hoặc đặt bằng 0 (tránh tầm thường, vì toàn bộ chuỗi luôn trùng chính nó).

Ví dụ S = "AABAAB" (tiền tố là "AAB..."):

Vậy z = [0, 1, 0, 3, 1, 0].

Nhận xét trực giác: z[i] > 0 nghĩa là "có một đoạn bắt đầu tại i mà hình dạng giống hệt phần đầu chuỗi", và đó là gợi ý để tìm pattern matching.