Z 演算法（Z-algorithm）

拿一個字串，在每個位置問一個簡單問題：從這裡開始，連續有幾個字元和字串最開頭相同？把這個數字寫在每個位置上，你就建好了 Z 陣列。它是字串如何回響自己開頭的所有方式的精簡指紋，而精確模式比對幾乎可以從中免費得出。

形式上，對字串 S，Z[i] 是「起始於位置 i、且同時是 S 之前綴」的最長子字串的長度（依慣例 Z[0] 不定義或設為整段長度）。以 S = "aabxaab" 為例：Z[1]=1（索引 1 的 "a" 對上前綴 "a"，但 "ab"!="aa"），Z[2]=0，Z[3]=0，Z[4]=3（索引 4 的 "aab" 對上前綴 "aab"），依此類推。巧妙之處在於用總計 O(n) 算出所有 Z 值。演算法維護一個「Z 盒」，即它已確認等於某前綴的最右區間 [l, r]。當它走到這個盒子內的新位置 i 時，已知盒子等於一個前綴，所以位置 i 的字元對應到位置 i-l 的字元；它從那裡複製已知的 Z 值當作起跑點，只在超出 r 時才做新的字元比較。由於每次新比較都把 r 往前推，而 r 只增不減，總比較工作是線性的。

要在文字 T 中比對模式 P，就對組合字串 P + '#' + T 建 Z 陣列，其中 '#' 是兩者都不出現的分隔符。在 T 部分裡，凡 Z 值等於 m（模式長度）的位置都標示一次精確出現——因為該處有 m 個字元對上前綴，而前綴就是 P。這給出 O(n+m) 的比對，而且許多人覺得它比 KMP 的失敗函數更容易推導與記憶。Z 陣列也是處理週期、重複的多用途工具，並可作為後綴結構建構中的踏腳石。