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).
prefix đang so
copy (B1)
extend (B2)
i hiện tại
trong Z-box
Bấm Khởi tạo để bắt đầu.
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.
separator $
z[i] == |P| (match)
Bấm "Tính & tìm match".
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.
Bấm "So sánh".