Z 陣列在量什麼
到目前為止，你已見過在每個對齊處都從頭重新檢查模式的暴力掃描，也看過 Knuth-Morris-Pratt 如何靠預先算出模式與自身的重疊來避開那份浪費。Z 演算法追逐的是同一個獎賞——線性時間的精確比對——但它對「一個」字串問出一個漂亮而具體的問題，並一次為每個位置給出答案。那個單一的答案，最後足以解決比對問題，以及許多其他字串難題，幾乎是免費附送。
固定一個長度為 `n` 的字串 `S`。Z 陣列為每個從 1 到 n-1 的索引 `i` 儲存值 `Z[i]` ＝ 從位置 `i` 開始、與從 `S` 最開頭開始的那一段「完全吻合」的最長延伸長度。換句話說：你能從位置 `i` 和從位置 0 同步往後讀 `S`，讀到多遠才會碰上兩個字元不一致（或讀到結尾跑出去）？位置 0 很特別，我們通常讓 `Z[0]` 不定義，因為整個字串在那裡理所當然地與自己吻合。
S = a a b a a b a a a idx 0 1 2 3 4 5 6 7 8 Z - 1 0 5 1 0 2 2 1 Z[3]=5: "aabaa" at pos 3 matches prefix "aabaa", then a vs b breaks Z[6]=2: "aa" at pos 6 matches prefix "aa", then 'a' vs 'b' breaks
從 Z 陣列到字串比對
一個關於「一個」字串的工具，憑什麼幫我們把模式 `P` 比對到文字 `T`？這裡有個一拍即合的訣竅。建一個新字串 `Glue = P + '#' + T`，其中 `#` 是一個既不出現在 `P`、也不出現在 `T` 的分隔字元。現在對 `Glue` 跑 Z 演算法。因為 `Glue` 的前綴正好就是 `P`，所以在 `T` 那一段裡任何 `Z[i]` 等於 `P` 長度的位置 `i`，都是 `P` 完整重現之處——那就是一次匹配。分隔符保證沒有任何虛假的重疊能把某個 Z 值延伸到超過 `P` 的尾端。
把位置換算回去：在 `Glue` 索引 `i` 找到的匹配，落在原始文字 `T` 的索引 `i - (len(P) + 1)`。所以對一個長度為 `len(P) + 1 + len(T)` 的字串跑一趟 Z 演算法，就回報出「所有」出現處。若令 `m = len(P)`、`n = len(T)`，這以 O(m + n) 時間執行——和 KMP 一樣的主標題成本，只是走了一條不同、甚至可說更簡單的路。
Z 盒：重用我們已經比對過的部分
若天真地計算，每個 `Z[i]` 可能花到 `n` 次比較，把整件事在最壞情況拖回 O(n^2)——正是暴力比對者掉進去的陷阱。Z 演算法靠隨身攜帶一個視窗逃脫，這個視窗就是 Z 盒，記為一個區間 `[l, r]`。這個盒子是我們目前為止發現、向右延伸最遠的「與前綴吻合的」匹配：子字串 `S[l..r]` 已知等於 `S[0..r-l]`，也就是 `S` 的一個前綴。整個加速就騎在一個觀察上：在那個盒子內，我們「已經」把那些字元和前綴比對過了，所以我們能複製舊答案，而不必重讀。
具體來說，假設我們正要計算 `Z[i]`，而 `i` 落在目前的盒子內，也就是 `i <= r`。因為 `S[l..r]` 鏡射著一個前綴，位置 `i` 的字元對應到 `S` 前端鏡射位置 `k = i - l` 的字元。我們已經知道 `Z[k]`。如果 `Z[k]` 小到能完整裝進盒子內（它沒有觸及邊界 `r`），那麼 `Z[i]` 就直接等於 `Z[k]`——完全不需要任何字元比較。鏡射免費地告訴了我們未來。
唯一需要真正動手的情況，是鏡射的答案會跑「超過」右緣 `r`。在那裡盒子的保證用完了——超過 `r` 之後，我們還從未把任何東西和前綴比對過——所以我們把 `Z[i]` 設為至少 `r - i + 1`（我們信得過的那部分），然後越過 `r` 用樸素的逐字元比較往後延伸，做法和暴力法一模一樣，但只在真正全新的地段上做。每當這次延伸把我們推過舊的 `r`，我們就把盒子向前滑到新的、更靠右的匹配。同樣的邏輯也處理 `i > r`（在任何盒子之外）：那裡我們直接從頭比較，並開一個新盒子。
為什麼它是線性的
成本分析是問題的核心，而它是一個漂亮的整體論證範例，而非逐步論證。把工作分成兩類。第一類是廉價的複製，`Z[i] = Z[k]`，每個花 O(1)；這種最多 `n` 個，所以合計 O(n)。第二類是當我們越過 `r` 延伸時、真正讀到新字元的昂貴字元比較。數清這些，才是巧妙之處。
- 每一次成功的比較（吻合）都讓右緣 r 恰好前進一個位置，因為我們只比較嚴格在目前 r 右側的字元。
- 邊界 r 在整趟執行裡只向右移動，且以 n-1 為上界，所以整個演算法成功比較的總次數最多是 n。
- 每個位置 i 最多觸發一次失敗的比較——就是結束它那次延伸的那一次——所以失敗次數同樣以 n 為上界。
- 全部加起來：O(n) 次複製，加上最多 n 次成功，加上最多 n 次失敗，得到總共 O(n)，且與字母表大小無關。
值得細品的關鍵洞見：一個字元在整趟執行裡最多被「新鮮地」讀一次（被一次延伸 `r` 的比較讀到），因為 `r` 從不後退。這和你或許記得的動態陣列加倍是同一種攤還味道——任何單一的 `Z[i]` 也許做了很多比較，但所有 `i` 的總和，被「一個只前進的指標能走多遠」這件事封頂。最壞情況、最佳情況、平均情況：每次都是 O(n + m)，沒有任何隱藏地取決於字串有多重複。
Z 與 KMP，以及該留意什麼
Z 陣列和 KMP 的前綴函數是近親：兩者都編碼了一個字串的自我重疊，而且你能在線性時間內機械地把一個轉換成另一個。實務上的差別大多是口味問題。KMP 以真正單一的串流方式逐一處理文字，從不需要事先把文字存起來，適合對著即時串流做比對。Z 的做法需要把串接 `P + '#' + T` 放進記憶體，但許多人覺得「這裡與前綴重新吻合多長」這個想法在壓力下更容易從零正確推導，圍欄樁的微妙細節也更少。
除了比對之外，Z 陣列是一把貨真價實的多用途工具。它能找出「同時也是前綴的最長子字串」、偵測一個字串的最小週期（對壓縮、以及辨認重複拼塊很有用）、並數出一個模式出現幾次——全都從一趟 Z 掃描以線性時間得到。它也自然地和更重的機器搭配：當你稍後遇到後綴陣列時，你會看見 Z 陣列正是那同一個「字串的各部分如何與其他部分一致」問題的廉價、單字串特例，而那些結構則以完全的一般性回答這個問題。