L42 — Z-Algorithm
z[i] = độ dài chuỗi con dài nhất bắt đầu tại i mà cũng là prefix của
toàn chuỗi. Z-box [l, r] tái dùng thông tin để tính trong O(n). Dùng Z cho
pattern matching, period, distinct substrings.
1. Z-array builder — Z-box di chuyển
Nhập chuỗi, bấm ▶ Tự chạy hoặc Bước → để xem từng z[i] được tính.
Khi i nằm trong box → copy (B1);
khi chạm biên box → extend (B2, so trực tiếp).
2. Z matching — ghép P + $ + T
Ghép W = P + $ + T, tính Z. Vị trí z[i] == |P| (ô xanh lá) là một match
của P trong T. Separator $ chặn match tràn qua ranh giới.
Thử: ghép P + "$" + T rồi dựng Z — mọi vị trí có Z ≥ |P| là một match: một mảng Z giải trọn bài string matching.
3. Z vs KMP — Z-array đối chiếu LPS
Trên cùng một chuỗi, so sánh Z-array (LCP với suffix tại i — nhìn về trước) và LPS (prefix=suffix dài nhất của S[0..i] — nhìn về sau). Cả hai cùng O(n), mã hóa cùng thông tin cấu trúc lặp.