假設要知道字串前綴在每個較後位置重新出現多長。把每個後綴獨立與前綴比較,做法正確,但高度重複的字串會令相同關係被反覆核查。全部字元相同時,這些獨立掃描需平方時間。
Z 陣列記錄全部這類前綴匹配長度。其線性時間計算會重用一段先前已驗證的匹配區間,稱為 Z-box。關鍵是:這個區間究竟證明了多少?有時它完全決定新答案,有時它只給下界,必須從右邊界繼續比較。
這個表示不同於 KMP 的前綴函數狀態。我們將推導它自己的不變量,再利用結果找精確模式出現位置、後綴邊界及週期。程式不依賴雜湊或帶概率的相等判定。
以明確邊界定義匹配長度
設 為長度 的序列,由 0 起編號。半開片段 包含位置 。元素以一致的相等關係比較;下文處理字串時,元素是 Python 字串碼位。不會暗中轉換大小寫、進行 Unicode 正規化或按字素群組分段。
定義 9.2.1
(Z 值與第零位置的約定)
對 ,定義 為滿足以下條件的最大長度 :
約定 ,不以它描述完整序列與自己的匹配。空序列的 Z 陣列也是空的。正位置的值為零,表示第一個元素已經不同。
上界 不可省略:匹配不能越過後綴末端。若 ,下一次比較失敗,所以 ;若 ,後綴已耗盡,該側沒有下一個元素可比。
例如 aaaaa 的 Z 陣列是 。即使每個可用元素都相同,後綴長度仍令數值遞減。若每次從零開始計算,就會重做 次成功比較。
已知匹配區間提供兩種不同資訊
定義 9.2.2
(Z 區間)
依次處理 時,維持一段已驗證區間 ,滿足
它的右端點,是先前已計算匹配所到達的最遠位置;起初 。較早的 Z 值都已精確。容許空區間。若 ,舊區間不能提供任何正長度資訊,便由零開始直接比較。
若 ,位置 在區間內。令 ,則位置 對應前綴位置 ,而 已算好。在區間範圍內,可以安全複製
上限 是舊區間還可提供的長度。它表示已證明資訊的邊界,並非斷言真正匹配一定在此終止。
定理 9.2.3
(區間重用)
設 ,,令 ,並設 已是精確值,記 。則 ,故 。若還有 ,則 。
證明
(把相等關係經區間搬過來)
對每個 ,區間等式給出 ,舊值 再給出 。所以頭 個元素確實與前綴相同。
若 ,複製前綴之後的失配也在舊區間內。精確舊值保證 ,而區間等式把右側元素對應到 。因此新匹配恰好在 結束,不可能更長。
若 ,已知相等到達區間邊界,但區間沒有證明下一個元素。真正匹配可能在此結束,也可能超過 。複製 個元素後,開始直接比較;遇到失配或序列末端,便得到精確新值。若新端點 超過 ,就把區間更新為 。
證明透視
上限把證明分成兩種情形
上限 把兩種用到不同類型事實的情形分開。當 時,證明用了兩個等式(區間和舊 Z 值)和一個不等式,即經區間搬過來的舊失配;正是這個不等式固定了答案。當 時,只有等式可用,它們至多保證 個元素,卻不保證任何不等式,這正是為甚麼必須從 重新開始直接比較。條件 保證使用 時它已是精確值。下面的反例顯示去掉上限會出甚麼問題。
所用 是較早的值:迴圈中可用的區間,必定從較早的正位置 開始,故 。實作可在複製之後統一執行比較迴圈;內部失配情況下,第一次比較只會確認已知失敗。
反例模式
超過舊區間複製,會虛構相等元素
對 aaab,位置 1 的匹配長度為 2,所以區間是 。到位置 2 時,、,但可用區間後段只有 。安全的複製長度是一。
下一次比較是前綴 a 與最後的 b,所以 。若盲目複製舊值 2,就會聲稱後綴 ab 匹配前綴 aa。舊值描述的是另一位置的匹配,多出來的元素不在這個區間所保證的相等範圍內。
同時展示兩種重用情況
例題 9.2.4
(內部答案固定;邊界答案可以增長)
取 aabcaabxaaaz,位置為 0 至 11。完整 Z 陣列是 。以下選取步驟展示兩種情況:
| 位置 | 比較前的資訊 | 精確值 | 之後的區間 |
|---|---|---|---|
| 4 | 在舊區間外;把 aab 與前綴比較 | 3 | |
| 5 | 、;搬用內部失配 | 1 | |
| 6 | 、 | 0 | |
| 8 | 在區間外;兩個 a 匹配,之後 a 與前綴 b 不同 | 2 | |
| 9 | 複製 ,再比較位置 10 | 2 | |
| 10 | 複製一個至邊界,再遇到最後的 z | 1 |
位置 9 複製的一個元素並非完整答案。下一個 a 也匹配前綴位置 1,所以長度增至二;最後的 z 再與前綴位置 2 的 b 失配。位置 5 則不同:失配已由區間內資訊保證,不可能成功延伸。
例題 9.2.5
(用盡的後綴,以及隨後的區間)
abcabc 的 Z 陣列是 。位置 1 和 2 立即失配,因為 b、c 都不同於 a。在位置 3,後綴 abc 與前綴相同並已用盡:,這同時顯示邊界 abc 與週期 3。此時區間是 。位置 4 的 ,而 ,所以直接搬用:。位置 5 的 ,,所以 。最後兩個值除了已知的失配之外,不需要新的比較。
為何全部比較工作只有線性
定理 9.2.6
(線性時間的 Z 陣列)
在索引與元素相等比較都是常數時間的假設下,這個迴圈計算長度為 的序列的 Z 陣列,需時 、使用 個儲存格。
證明
(把成功的比較記在位置上)
外層每次迭代只做常數工作來選初始長度。若複製匹配嚴格在舊區間內結束,已知失配使它沒有任何成功比較。否則直接比較由舊右端點 或更後位置開始。
把每次成功比較記在它的後綴側位置上。同次迭代中,這些位置逐個遞增;迭代結束時,新區間已伸至每個這類位置之後。因為 不會減少,較後迭代不可能再在已記帳位置成功比較。可記帳位置只有 1 至 ,至多 個。
每次迭代也至多有一次失敗元素比較,因為迴圈遇到首個失配便停止;序列耗盡則可能不用失敗比較就停止。 時共有 次迭代,因此全部元素比較及其餘迴圈工作都是 。這裏有內層比較迴圈,不代表時間必然平方。
證明透視
為甚麼區間右端是一個棘輪
每次成功的直接比較都發生在某個後綴位置 。在內部失配的情形下沒有任何比較成功;在到達邊界的情形下,比較從 開始;當 時,比較從 開始。迭代結束後 ,而 從不減少,所以 不可能再被成功比較。因此記帳的對象是位置而不是迭代,這就是為甚麼外層迴圈裏的內層迴圈不會使成本相乘。失敗的比較每次迭代至多多一次。
Z 陣列使用 個單元,區間本身只需常數狀態。這些界假設按索引存取及元素相等比較都是常數時間。如果比較一個元素本身就要長時間,界也要重新計算。
用不會碰撞的分隔元素做精確匹配
設非空模式 長 ,文字 長 。把模式、一個全新分隔元素、文字接成同一元素序列。文字從偏移 開始。
定理 9.2.7
(由 Z 值得到出現位置)
設 非空、長 , 長 , 是序列 ,其中元素 不等於 或 的任何元素。對 ,有 ,並且 在 的下標 出現,當且僅當 。
證明
(全新分隔元素把每個值限制在 m 以內)
文字下標 處,頭 個元素與合併序列前綴相同,當且僅當模式在 出現。全新分隔元素更保證該 Z 值不能超過 :匹配 個元素後,前綴提供分隔元素,後綴則提供文字元素,或者文字已結束。所以 z[m + 1 + j] == m 是精確出現判定。
Python 字串由字元元素組成,因此把新建立的 object() 放入串列,就有一個與所有字元都不相等的分隔元素。不必猜測某個特定字元,例如 #,是否沒有出現在兩個輸入內。下列包裝函數使用此物件作分隔,按遞增次序傳回出現下標,包含重疊出現。
def z_array(sequence):
n = len(sequence)
z = [0] * n
left = right = 0
for i in range(1, n):
if i < right:
z[i] = min(right - i, z[i - left])
while i + z[i] < n and sequence[z[i]] == sequence[i + z[i]]:
z[i] += 1
if i + z[i] > right:
left, right = i, i + z[i]
return z
def all_occurrences(pattern, text):
if pattern == "":
return list(range(len(text) + 1))
combined = list(pattern) + [object()] + list(text)
z = z_array(combined)
length = len(pattern)
offset = length + 1
return [i for i in range(len(text)) if z[offset + i] == length]
包裝函數接受字串;低層函數接受符合先前相等假設、有限且可按索引存取的元素序列。兩者都不修改輸入。建立合併串列、計算 Z 陣列及掃描文字位置,共需 時間和儲存單元,包含至多 個位置的輸出。空模式的指定結果是全部邊界 ,在建立合併序列之前處理。
例題 9.2.8
(保留重疊出現,而非消耗第一次匹配)
模式為 aba,文字為 ababa。顯示時以 表示獨特分隔元素;這個符號代表物件,不是選定的輸入字元。合併元素是 a b a、、a b a b a,Z 陣列為 。
文字偏移是 。合併位置 4、6 的值都等於模式長度 3,所以結果為 。兩次出現共享文字位置 2 的元素。從 Z 陣列檢查每個起點,便保留這個重疊,而不是越過第一次完整出現才繼續。
反例模式
普通分隔字元不能證明長度上限
假設模式 #、文字 ##,再以一個字面 # 分隔,合併結果是 ####,Z 陣列為 。第一個文字位置的 Z 值為 2,並非模式長度 1,因為相等越過了所謂分隔字元。
若使用等於模式長度的篩選,就會漏掉文字下標 0 的出現。改用大於或等於仍可找出它,但「這些 Z 值不超過模式長度」的聲稱已不成立。全新物件建立了本實作真正使用的不變量;顯示一個標點符號,並不證明它獨特。
邊界與週期沿用同一批精確值
定理 9.2.9
(由 Z 值得到邊界與週期)
設 長 ,。後綴 是 的真邊界,當且僅當 ,此時其長度為 。對 , 是 的週期,當且僅當 。
證明
(把整個後綴與前綴比對)
非空真邊界,是同時為前綴及後綴、長度 滿足 的片段。該後綴由 開始,判定就是 :完整後綴匹配前綴。定義中的上界令該位置不可能有更大值。掃描這些後綴起點,就在線性時間列出全部真邊界長度。
對 ,若每個 都有 ,便稱 是週期。這正是位置 的 次前綴對後綴比較,所以判定為 。 時,完整長度 是平凡週期,但陣列沒有合法位置 z[n],不能以該索引測試。
常見錯誤
(週期不等於完整重複)
週期不必整除長度。ababa 有 ,故 2 是週期,但字串不是若干份完整 ab 的串接。若要求長度 區塊的完整重複,還須 整除 。這分清「下一份只寫了一部分便結束」的重複規律與完整份數的串接。
常見錯誤
(Z 值不是 KMP 的邊界長度)
共同有用的資訊,是已證明兩個片段相等。Z 值不是任意子字串較早出現的長度,也不是 KMP 在該位置結束的前綴之邊界長度。每次使用時,都應保留它「前綴對目前後綴」的含義。
概念視角組合
從 Z 值讀出前綴函數
對位置 , 的一個長度為 的真邊界,起始於某個 ,並滿足 ,即 。最長邊界來自最小的這種 ,所以 ;若不存在這樣的 ,則 。每個 Z 區間 列出了從 起始的邊界仍然成立的結尾位置。
練習與完整解答
快速檢查
(1. 採 z[0]=0,寫出 aaaaa 的 Z 陣列。找到區間 [1,5) 後,到位置 2 時為何不能不加上限地複製 z[1]=4?)
解答 · 1. 可用後綴限制可複製資訊
陣列為 。位置 2 的區間只提供 個元素,整個後綴也只有三個。複製 4 會越過序列末端。加上上限的初始值為 ,而耗盡序列證明它就是精確答案。
快速檢查
(2. aabcaabxaaaz 中,為何位置 5 的值恰好是 1,而位置 9 複製的 1 可以增加至 2?)
解答 · 2. 找出第一個未證明的比較
位置 5 的區間 還有兩個元素,但 嚴格在區間內結束。失配經區間搬到新位置,令答案固定為 1。位置 9 的區間 卻只剩一個元素,所以複製的 1 到達邊界。位置 10 是新資訊,其 a 匹配前綴位置 1,長度增至 2,之後最後的 z 才與前綴 b 失配。
快速檢查
(3. 在文字 ababa 找模式 aba,合併文字偏移是多少?哪兩個合併 Z 值證明出現位置?為何不跳過下標 2?)
解答 · 3. 把合併索引轉回文字索引
偏移為 。合併位置 4、6 的 Z 值是 3,所以文字起點為 及 。方法檢查每個文字起點,而非消耗一次匹配後就跳過整個長度,因此保留重疊出現。
快速檢查
(4. 為何用字面 # 作分隔時,在文字 ## 找模式 # 會令等於長度的篩選失效?object() 的哪個性質恢復了本實作的證明?)
解答 · 4. 證明獨特,而非假設某字元缺席
合併字串是 ####,第一個文字 Z 值是 2,所以即使該處有匹配,等於模式長度 1 的判定也失敗。全新物件元素與所有字元不同;模式匹配完後,下一前綴元素是物件,後綴則已結束或提供字元,所以匹配不能超過一。兩個文字起點的 Z 值因而都為 1。
快速檢查
(5. 空模式在文字 ab 中,all_occurrences 應傳回甚麼?非空模式配空文字,以及模式長於文字時,又如何?)
解答 · 5. 空匹配位於邊界
空模式配 ab,結果為 ,每個邊界一個。非空模式在空文字中沒有出現,傳回 ;模式長於文字也傳回 ,因為任何剩餘後綴都沒有足夠元素。這些結果來自包裝函數的明確約定及後綴長度上限,不需要改變 的含義。
快速檢查
(6. ababa 的 Z 陣列為 [0,0,3,0,1],求非空真邊界長度。2 是否週期?字串是否由長度二區塊的完整份數組成?)
解答 · 6. 週期可以在不完整的一份結束
位置 2、4 分別以長度 3、1 耗盡後綴,所以真邊界長度為 及 。由 ,2 是週期。但 2 不整除 5,所以字串不能由完整長度二區塊串接而成;它只沿 ab 的重複規律,寫到下一份的首個元素為止。