Nguồn bài: Codeforces
Trước khi đọc bài này, các bạn có thể đọc bài Xử lý xâu để nắm được các thuật ngữ cơ bản.
Z Algorithm hay còn gọi là Z Function là thuật toán áp dụng cho các bài so khớp chuỗi.
Cho một chuỗi có độ dài , thuật toán Z Function tạo ra một mảng mà tại mỗi vị trí , ta có là độ dài chuỗi con dài nhất là tiền tố của bắt đầu tại vị trí , hay nói một cách khác là một số nguyên lớn nhất mà với mọi . Trường hợp thì .
Ta duyệt qua tất cả các ký tự của (chỉ số từ 1 đến ). Trong quá trình duyệt, ta duy trì một đoạn với là một số lớn nhất thỏa và là một tiền tố của (Nếu không xuất hiện các đoạn như vậy thì đặt ).
Với ta có thể dễ dàng tính và bằng phép so sánh với . Đồng thời, ta có thể tính giá trị .
Giả sử ta đã xây dựng được đoạn và các giá trị , ta sẽ tính và cập nhật đoạn mới như sau:
Nếu , khi đấy không tồn tại một chuỗi con là tiền tố của bắt đầu tại một vị trí trước và kết thúc tại ví trí hoặc sau . Bởi nếu như có một tiền tố như vậy, thì đoạn sẽ là chuỗi tiền tố tối ưu chứ không phải . Do đó, ta sẽ cập nhật lại đoạn bằng cách so sánh với và lấy giá trị hiện tại ().
Ngược lại, thì đoạn hiện tại kéo dài ít nhất đến . Đặt . Ta biết rằng bởi vì bằng với ít nhất là ký tự. Xét các trường hợp sau:
Tại mỗi bước trong vòng lặp, chúng ta không cần so sánh ký tự tại các vị trí nhỏ hơn , và mỗi lần ký tự phù hợp thì ta tăng lên một, vì thế ta sẽ tốn nhiều nhất phép so sánh. Ngoài ra, với mỗi giá trị , ta chỉ tìm thấy một ký tự không phù hợp (điều kiện tăng ). Vì thế không thể có nhiều hơn phép so sánh cho kết quả sai. Đưa đến độ phức tạp thuật toán là .
Có thể dễ dàng cài đặt. Chú ý việc tối ưu hóa được sử dụng khi (Điều đó không làm ảnh hưởng đến thuật toán kể từ giá trị kế tiếp không phân biệt).
int L = 0, R = 0;
Z[0] = n;
for (int i = 1; i < n; i++)
if (i > R)
{
L = R = i;
while (R < n && S[R] == S[R - L]) R++;
Z[i] = R - L; R--;
}
else
{
int k = i - L;
if (Z[k] < R - i + 1) Z[i] = Z[k];
else
{
L = i;
while (R < n && S[R] == S[R - L]) R++;
Z[i] = R - L; R--;
}
}
Có thể dùng ZFuntion để giải bài này. Ta tạo ra một chuỗi , sao đó xây dựng mảng . Những vị trí có (Với ) là vị trí tương ứng của trong .