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] để 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); tìm chu kỳ ngắn nhất của chuỗi. Z-function và failure function của KMP là hai mặt của cùng ý tưởng prefix — 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 "prefix thông minh" 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

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 — 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" — chính là gợi ý để tìm pattern matching.

2. Tính O(n) bằng z-box

2.1 Ý tưởng z-box

Z-box [l, r] là đoạn [l, r-1] xa nhất bên phải mà ta đã biết là trùng với tiền tố S[0..r-l-1]. Tức là: S[l..r-1] = S[0..r-l-1] và r là lớn nhất tại thời điểm đang xét.

Khi tính z[i]:

• Nếu i >= r: không có thông tin, so sánh thủ công từ đầu, cập nhật [l, r] nếu r mới lớn hơn.
• Nếu i < r (nằm trong box): biết S[i..r-1] = S[i-l..r-l-1]. Gọi k = i - l, ta đã có z[k].
  • Nếu z[k] < r - i: đoạn trùng nằm gọn trong box → z[i] = z[k] (không cần so thêm).
  • Nếu z[k] >= r - i: đoạn trùng chạm hoặc vượt biên r → z[i] ít nhất là r - i, nhưng có thể dài hơn → so tiếp từ S[r] và S[r-l], cập nhật [l, r].

Nhờ hai trường hợp này, mỗi ký tự được so sánh tối đa một lần khi mở rộng box → tổng O(n).

2.2 Pseudocode

function computeZ(S):
    n <- S.length
    z <- mảng n phần tử, z[0] = 0
    l <- 0
    r <- 0                              -- z-box hiện tại [l, r)
    for i from 1 to n-1:
        if i < r:                       -- i nằm trong box
            k <- i - l
            if z[k] < r - i:            -- trùng gọn trong box
                z[i] <- z[k]
                continue                -- không cần so thêm
            else:                       -- chạm biên, cần mở rộng
                z[i] <- r - i          -- ít nhất r-i ký tự trùng
        else:
            z[i] <- 0                  -- ngoài box, bắt đầu từ 0
        -- mở rộng thủ công từ z[i] ký tự đã biết
        while i + z[i] < n and S[z[i]] = S[i + z[i]]:
            z[i] <- z[i] + 1
        -- cập nhật box nếu đạt xa hơn bên phải
        if i + z[i] > r:
            l <- i
            r <- i + z[i]
    return z
// Time: O(n)  Space: O(n)

2.3 Trace S = "AABAAB"

Khởi đầu: l=0, r=0, z=[0,0,0,0,0,0]. Ký hiệu [l,r) — biên phải r là exclusive.

Kết quả z = [0, 1, 0, 3, 1, 0] — khớp bảng định nghĩa ở mục 1.

Để ý hai bước cuối: tại i=4 và i=5, con trỏ nằm trong box [3,6) mới mở (do z[3]=3). Ta tái dùng ngay z[k] mà không so sánh ký tự nào — đây chính là chỗ z-box tiết kiệm so với so từ đầu.

3. Ứng dụng: pattern matching O(n+m)

3.1 Ý tưởng ghép chuỗi

Để tìm pattern P trong text T, ghép chúng thành chuỗi mới:

S = P + '#' + T

Ký tự '#' (separator) không xuất hiện trong cả P lẫn T — đảm bảo z-value tại vị trí trong T không vượt quá |P|.

Sau khi tính z cho S:

• Với mọi vị trí i trong phần T của S (tức i >= |P| + 1), nếu z[i] = |P| thì P xuất hiện tại vị trí i - |P| - 1 trong T.

3.2 Pseudocode

function ZSearch(T, P):
    m <- P.length
    S <- P + '#' + T                    -- nối chuỗi với separator
    z <- computeZ(S)
    matches <- danh sách rỗng
    for i from m+1 to S.length-1:
        if z[i] = m:                    -- khớp hoàn toàn pattern
            matches.append(i - m - 1)  -- vị trí trong T
    return matches
// Time: O(n+m)  Space: O(n+m)

Ví dụ: P = "AB", T = "ABABC", S = "AB#ABABC".

z của S:

• z[0]=0 (quy ước)
• z[1]=0 (B≠A)
• z[2]=0 (#≠A)
• z[3]=2 (AB=AB) → khớp tại T[0]
• z[4]=0 (B≠A)
• z[5]=2 (AB=AB) → khớp tại T[2]
• z[6]=0 (B≠A)
• z[7]=0 (C≠A)

Pattern "AB" xuất hiện tại vị trí 0 và 2 trong T — đúng.

flowchart LR
    subgraph S["S = P + '#' + T"]
        P1["P[0]"] --- P2["P[1]"] --- SEP["'#'"] --- T0["T[0]"] --- T1["T[1]"] --- T2["T[2]"] --- T3["T[3]"] --- T4["T[4]"]
    end
    T0 -->|"z = dài P"| MATCH1["Khớp tại T[0]"]
    T2 -->|"z = dài P"| MATCH2["Khớp tại T[2]"]

3.3 Tại sao separator cần thiết?

Không có #, khi tính z[|P|] (ngay đầu phần T), box có thể mở rộng vào trong P → z[i] có thể vượt |P| và vị trí báo là "khớp" dù text chỉ khớp một phần P. Separator cắt đứt khả năng đó: z[i] tại phần T không bao giờ vượt |P| vì sẽ gặp # trước.

4. Ứng dụng: tìm chu kỳ ngắn nhất

Chuỗi S có chu kỳ (period) p nếu S[i] = S[i - p] với mọi i >= p — tức dịch chuỗi sang phải p bước thì phần chồng lấn trùng khớp. Lưu ý: định nghĩa này cho phép bản lặp cuối dở dang (ví dụ "ABCAB" có chu kỳ 3 vì S[3]=S[0], S[4]=S[1], dù "AB" cuối chưa đủ một "ABC"). Chu kỳ ngắn nhất liên quan trực tiếp đến z-array:

p là một chu kỳ của S khi và chỉ khi z[p] >= n - p — đoạn từ p đến cuối (dài n-p) trùng với tiền tố.

Vậy chu kỳ ngắn nhất là p nhỏ nhất thoả z[p] >= n - p.

function shortestPeriod(S):
    n <- S.length
    z <- computeZ(S)
    for p from 1 to n-1:
        if z[p] >= n - p:              -- đoạn từ p đến cuối trùng tiền tố
            return p                   -- p là chu kỳ ngắn nhất
    return n                           -- chuỗi không lặp — chu kỳ = chính nó
// Time: O(n)  Space: O(n)

Ví dụ: S = "ABCABC", n=6. Tính z:

z[3]=3 >= 6-3=3 → p=3 là chu kỳ → "ABC" lặp 2 lần. Đúng.

flowchart LR
    S0["A"] --- S1["B"] --- S2["C"] --- S3["A"] --- S4["B"] --- S5["C"]
    S3 -.->|"z[3]=3, khớp tiền tố"| S0
    S3 -.->|"p=3 là chu kỳ"| PER["Chu kỳ ngắn nhất = 3"]

5. So sánh Z-function và Failure Function (KMP)

Hai cấu trúc giải cùng lớp bài nhưng nhìn từ góc khác:

Hai cấu trúc đều O(n) và đều giải được bài matching, period, lặp. Chọn cái nào là sở thích cá nhân — Z-function thường dễ code hơn trong thi đấu vì logic z-box tuyến tính và không có edge case "j về 0".

6. Pitfall

Pitfall 1 — Quên separator hoặc dùng separator xuất hiện trong input

-- SAI: separator '/' có thể xuất hiện trong path string
S <- P + "/" + T

-- DUNG: dùng ký tự KHÔNG xuất hiện trong cả P lẫn T
-- Với DNA (A/C/G/T): dùng '$'
-- Với số nguyên: dùng -1 (nếu lưu mảng số)
-- Với chữ cái thường: dùng '#' hoặc '$'

Nếu separator xuất hiện trong T, z[i] tại vị trí đó có thể bằng |P| dù không thực sự khớp — báo false positive.

Pitfall 2 — Nhầm biên box inclusive: dùng i <= r thay vì i < r

Box được định nghĩa nửa mở [l, r) — r là exclusive (ký tự tại r chưa chắc khớp). Nếu kiểm tra "i trong box" bằng i <= r, thì khi i = r ta sẽ tái dùng z[i-l] cho một vị trí thực ra nằm ngoài vùng đã biết → kết quả sai.

-- SAI: i = r van bi coi la "trong box"
if i <= r:                  -- BUG: r exclusive, i=r la NGOAI box
    k <- i - l
    z[i] <- min(z[k], r - i)   -- r-i = 0 -> z[i]=0 sai khi le ra phai so thu cong

-- DUNG: r exclusive nen dung i < r
if i < r:
    k <- i - l
    if z[k] < r - i: z[i] <- z[k]
    else: z[i] <- r - i        -- roi mo rong thu cong tu day

Điều kiện cập nhật box if i + z[i] > r (dùng >) thì đúng — chỉ dời box khi vươn xa hơn biên phải hiện tại. Lỗi nằm ở phép kiểm tra "i có trong box không", phải là i < r vì r exclusive.

Pitfall 3 — Dùng z-array để matching nhưng tính z trên T alone thay vì P+'#'+T

-- SAI: tính z trên T, tìm vị trí z[i] = |P|
z_T <- computeZ(T)
-- Không liên quan! z_T[i] so T[i..] với T[0..], không liên quan P

-- DUNG: LUÔN nối P + separator + T
S <- P + '#' + T
z <- computeZ(S)
-- Tìm z[i] = |P| với i >= |P|+1

Z-array tính trên T đơn thuần đo "đoạn từ i trùng bao nhiêu với tiền tố của T" — hoàn toàn khác bài toán tìm P trong T.

7. Liên hệ các bài khác

• KMP — failure function: Z-function và failure function là hai mặt của ý tưởng "tiền tố thần kỳ". KMP tái dùng thông tin theo chiều "dịch j", Z-function tái dùng theo chiều "z-box trượt phải". Hai cấu trúc có thể chuyển đổi qua lại — hiểu cả hai giúp phân tích bài từ hai góc.
• Rabin-Karp: Hướng hoàn toàn khác (hash thay vì prefix structure). Rabin-Karp mạnh hơn cho bài đa mẫu khi cần tìm nhiều pattern cùng lúc (multiset hash); Z-function sạch hơn cho bài đơn pattern.
• Aho-Corasick: Nếu Z-function giải đơn pattern bằng ghép chuỗi, Aho-Corasick giải tập pattern bằng automaton trên trie. Failure link của Aho-Corasick tổng quát hoá lps của KMP lên cây — không có analogue trực tiếp với z-array.
• Naive matching: Z-function là nâng cấp trực tiếp — cùng bài toán "tìm P trong T" nhưng O(n+m) thay vì O(n·m), nhờ z-box tránh so sánh thừa.

📚 Deep Dive

Tóm tắt

• z[i] = số ký tự bắt đầu từ i trùng với tiền tố của S — định nghĩa trực quan, dễ hiểu hơn lps.
• Z-box [l, r) lưu đoạn xa nhất bên phải đã biết trùng tiền tố; tái dùng z[i-l] khi i < r → O(n) tổng thể (mỗi ký tự mở rộng box tối đa một lần).
• Matching: ghép P + '#' + T, tìm z[i] = |P| với i >= |P|+1 — separator ngăn box vượt biên pattern.
• Chu kỳ ngắn nhất: tìm p nhỏ nhất sao cho z[p] >= n - p.
• Z-function và failure function (KMP) tương đương về sức mạnh — Z-function thường dễ code hơn trong thi đấu.
• Pitfall thường gặp: separator sai, nhầm điều kiện box exclusive/inclusive, tính z trên T đơn thuần thay vì P+'#'+T.

Tự kiểm tra

Bài tiếp theo: Aho-Corasick — automaton so khớp đa mẫu