搜尋文字時,常會先匹配模式開頭好幾個字元,卻在下一個字元失敗。若直接由下一個文字位置重新開始,就會丟掉資訊:已匹配部分的某個後綴,可能本來就是有效的模式前綴。KMP 記錄的正是這些可重用前綴。
重點不只是更快把索引往回移。每次回退都必須保留對已讀字元的精確敘述。本節從前後綴推導回退規則,證明全部比較工作的線性界,並解釋如何在一次完整匹配後保留重疊出現的可能。
同時是前綴與後綴的字串
定義 9.1.1
(真前後綴與前綴函數)
非空字串 長度為 。若某個前綴同時也是後綴,且長度嚴格小於 ,便稱為真前後綴(proper border)。容許長度零的空字串。
模式 從零索引。定義 為前綴 的最長真前後綴長度。因此 ,而 。
本節所有索引及匹配位置均由零開始。Python 的 P[:i + 1] 就是這裏的 。
ababa 的非空真前後綴為 a 和 aba,長度一及三。整個字串也是前綴與後綴,但「真」排除了它。ab、abab 都不是後綴。這要求整段子字串相等,不只是頭尾某個字元相同。
引理 9.1.2
(前後綴的前後綴)
設 是字串 的真前後綴,長度為 。對每個 , 是 的前後綴長度,當且僅當它是 的前後綴長度。因此,對模式 ,數列 (只要項為正就繼續)按遞減次序列出 的全部真前後綴長度,最後是 。
證明
(較短前後綴藏在最長前後綴之內)
設 是 長度為 的前後綴。對 , 的長度 前綴等於 的長度 前綴,因 是前綴; 的長度 後綴也等於 的長度 後綴,因 亦是後綴。
因此, 是 的前後綴長度,充要條件是它亦為 的前後綴長度。最長長度 之後,下一個可行較短長度,就是該前後綴自身的最長真前後綴。
模式的長度 前後綴是 P[:j],其最長真前後綴長度為 。反覆跟隨這些值,便以遞減次序列出所有較短候選,最後到零。
以延長既有前後綴建立前綴函數
假設已知 ,令 。上一個前綴已以 P[:j] 結束。若新字元 等於 ,此前後綴便可延長至 。
若不同,較短前後綴仍可能延長。引理指出下一候選為 。反覆檢查直到成功或 。到零後與 比較,相等給長度一,不等給長度零。
定理 9.1.3
(前綴函數的遞推式)
對 ,令 ,並在 時令 ,使這條鏈止於 。則 ,其中 是鏈上第一個滿足 的項;若鏈上沒有項滿足 ,則 。
證明
(第一個成功延長的就是最長者)
若 有長度 的非空真前後綴,去掉最後字元後,便得到上一個前綴長度 的前後綴。延長所需比較正是 與 。
算法從上一個最長候選開始,沿完整的遞減鏈列出其餘較短候選。每次失敗都以必要的字元比較排除該長度,因此第一個成功者給出最大新長度。若全失敗,只剩空前後綴。對 歸納,便證明此遞歸規則正確。
例題 9.1.4
(一次不匹配,可以觸發多次回退)
模式 ababaca 的表格為
| 索引 | |||||||
|---|---|---|---|---|---|---|---|
| 字元 | a | b | a | b | a | c | a |
處理索引 5 之前,ababa 的最長前後綴為 aba,長度三。新字元 c 不等於 ,故回退至 ;也不等於 ,再回退至 ;與 仍不同,所以 。
候選長度為 ,全部是真正的前後綴長度。下一個 a 則重新建立長度一的前後綴。
在文字上維持同一個不變量
模式長度為 ,文字長度為 。每次讀取新字元之前,令 等於目前已讀文字的後綴中,長度嚴格小於 的最長模式前綴長度,初始為零。
下一字元先與 比較。若不等且 ,以 取代 ,仍針對同一文字字元重試;相等則把 加一;在零處仍不等就保留零。
若 ,表示完整匹配剛在文字索引 結束,起點為 。報告後,在讀下一字元前設 。
定理 9.1.5
(掃描不變量與所報告的出現位置)
採用上述失配回退與完整匹配後的重設,則在讀入文字字元之間, 是「長度小於 且為已讀文字後綴的最長模式前綴」的長度;並且每個出現位置恰好在讀入其最後一個字元時被報告一次。
證明
(回退與重設恰好保留有用的後綴)
讀新字元前,已匹配後綴為 P[:j]。任何也符合已讀文字後綴的較短模式前綴,都必須是這段已匹配字串的前後綴。因此,前後綴鏈列出全部可行較短狀態,而不必重讀較早文字字元。
延長成功時,較長候選均已失敗,所以新 是最長匹配前綴。若達 ,已讀文字以整個模式結束,證明所報出現正確。繼續搜尋時,這次出現的最長較短模式前綴後綴,恰為其最長真前後綴,長度 。
因此,報告出現後也恢復讀字元之間的不變量。每個可能結束位置都有檢查,不會遺漏出現;保留的後綴亦可能是下一個重疊出現的開頭。
證明透視
前後綴引理在兩處發揮作用
同一個引理讓不變量通過兩種不同的動作。失配時,回退 沿著已匹配字串 P[:j] 的前後綴往下走,這些恰好就是較短的候選狀態,所以沒有狀態被跳過。完整匹配之後,已讀的字串就是整個模式,其最長真前後綴的長度是 ;重設為此值,會保留可能開始下一個出現位置的最長後綴,重設為零則會把它丟掉。每次回退之後,同一個文字字元會再被比較,所以候選狀態被淘汰,只是因為它的下一個字元失配,絕不是因為它的長度小。
例題 9.1.6
(保留前後綴,才能找到重疊出現)
在 aaaaa 搜尋 aaa,其前綴表為 [0, 1, 2]。文字索引 2 結束第一個匹配,起點為零。重設 ,因最後兩個字元已匹配 aa。
下一個 a 完成起點一的出現;再作同樣重設,最後一個 a 完成起點二的出現。輸出為 [0, 1, 2]。若第一次後直接重設零,就丟掉重疊起點所需資訊。
同樣,aba 在 ababa 的起點為 [0, 2]。末尾前後綴 a 把一次出現的結尾資訊傳到下一次。
任意減一,甚至會產生錯誤匹配
反例模式
把回退換成 j 減一,會破壞不變量
模式為 ababc,文字為 ababbc。讀完開頭四字元 abab 時,匹配長度為四。下一文字字元 b 與預期的 c 不同。
錯誤地回退至三,便宣稱 aba 是已讀 abab 的後綴,實際長度三後綴卻是 bab。當前 b 隨後與模式位置三匹配,最後 c 又看來完成整個模式,錯誤報告起點一;但該視窗是 babbc,不是 ababc。
正確回退為 ,這些狀態都不能用當前 b 延長,所以沒有匹配。回退需要子字串相等作理據,不是只要數值變小就可以。
這個互動圖重現下面練習題的方法,包括上面的錯誤匹配例子。若想獨立練習,請先嘗試題目。選擇錯誤匹配示例、搜尋視圖及遞減規則,可查看無效回退。
回退狀態必須對應真正的後綴
逐次比較追蹤前綴表建立或模式搜尋。回退會用同一輸入字元再試;完整匹配後保留邊界,才能找到重疊出現。
已在第一個事件。
模式 P: ababaca; 文字 T: abababacaba.
初始狀態 · 追蹤事件 0/8
此階段的輸入: 模式 P; 已消耗字元數: 1; j: 0 → 0.
- [0]a
- [1]b
- [2]a
- [3]b
- [4]a
- [5]c
- [6]a
字元比較: 無.
比較使用舊 j;下方子字串聲稱使用新 j。回退不會前進輸入位置。
| 索引 | 字元 | 最長真邊界長度 π |
|---|---|---|
| 0 | a | 0 |
| 1 | b | 尚未計算 |
| 2 | a | 尚未計算 |
| 3 | b | 尚未計算 |
| 4 | a | 尚未計算 |
| 5 | c | 尚未計算 |
| 6 | a | 尚未計算 |
目前狀態聲稱甚麼: j=0
- 模式前綴 P[:j]
- ε
- 已消耗輸入的長度 j 後綴
- ε
兩個子字串相等: 是.
可處理下一字元. 已恢復最長可用狀態: 是.
最長狀態檢查只用於字元之間。回退時,較長後綴仍可能匹配舊輸入,只是已無法延伸目前字元。
完成前處理後才顯示完整模式的結果。
此階段建立 π,不搜尋文字。
| 追蹤事件 | 動作 | 輸入索引 i | 已消耗字元數 | j:之前 → 之後 | 字元比較 | 累計字元比較數 | 已報告起點 | 兩個子字串相等 | 已恢復最長可用狀態 |
|---|---|---|---|---|---|---|---|---|---|
| 初始狀態 | 1 | 1 | 0 → 0 | 無 | 0 | 不適用 | 是 | 是 | |
| 零狀態不等:消耗字元 | 1 | 2 | 0 → 0 | b ≠ P[0]=a | 1 | 不適用 | 是 | 是 | |
| 相等:延伸並消耗字元 | 2 | 3 | 0 → 1 | a = P[0]=a | 2 | 不適用 | 是 | 是 | |
| 相等:延伸並消耗字元 | 3 | 4 | 1 → 2 | b = P[1]=b | 3 | 不適用 | 是 | 是 | |
| 相等:延伸並消耗字元 | 4 | 5 | 2 → 3 | a = P[2]=a | 4 | 不適用 | 是 | 是 | |
| 不等:回退而不消耗字元 | 5 | 5 | 3 → 1 | c ≠ P[3]=b | 5 | 不適用 | 是 | 不適用 | |
| 不等:回退而不消耗字元 | 5 | 5 | 1 → 0 | c ≠ P[1]=b | 6 | 不適用 | 是 | 不適用 | |
| 零狀態不等:消耗字元 | 5 | 6 | 0 → 0 | c ≠ P[0]=a | 7 | 不適用 | 是 | 是 | |
| 相等:延伸並消耗字元 | 6 | 7 | 0 → 1 | a = P[0]=a | 8 | 不適用 | 是 | 是 |
- 輸入索引 i
- 1
- 匹配長度 j
- 0
- 已消耗字元數
- 1
- 前處理字元比較數
- 0
- 此階段目前字元比較數
- 0
- 目前已報告起點數
- 不適用
- 兩個子字串相等
- 是
- 最終報告完整且正確
- 不適用
追蹤事件 0/8: 初始狀態; j=0; 兩個子字串相等: 是. 最長狀態檢查只用於字元之間。回退時,較長後綴仍可能匹配舊輸入,只是已無法延伸目前字元。
為何邊界能支持重用
真邊界同時是前綴和後綴,而且比整個字串短;允許空字串。若已匹配字串的邊界長度為 j,下一個較短邊界的長度便是 π[j−1]。沿連結走,才會恰好遍歷其餘可能的後綴狀態,而非猜測一個較小數字。
ababaca 的 π=[0,0,1,2,3,0,1]。處理索引 5 的 c 前,匹配邊界長度為 3。同一個 c 依次與 P[3]=b、P[1]=b、P[0]=a 失配,候選為 3→1→0。改變的只有候選,不會退回較早的輸入索引重讀字元。
在兩個文字字元之間,j 是已消耗文字的後綴中,長度小於 m 的最長模式前綴。測試字元時,較長候選已被排除為無法延伸,因此回退候選不必是舊文字的最長後綴。完整出現後,重設至 π[m−1] 才恢復字元之間的不變式。搜尋 aaa/aaaaa 時,保留 j=2 得起點 0、1、2;歸零則只得 0。
把 j 減一不能代替邊界連結。模式 ababc、文字 ababbc 中,已消耗的 abab 並不以模式前綴 aba 結尾。回退 4→3 捏造這項相等關係,最後錯報起點 1;其視窗 babbc 不等於 ababc。正確鏈 4→2→0 不會報告出現。須分別核對錯報位置和遺漏的有效位置。
每次成功比較使 j 加一;每次失配回退至少減一。前處理最多有 m−1 次增加,搜尋最多有 n 次。因此本圖記錄的邏輯比較數分別不超過 max(0,2m−2) 及 2n。兩階段的演算法工作量合計 O(m+n),另需輸出儲存空間。這不表示每個輸入字元只比較一次。
長度 m 的字串若有長度 b 的邊界,便有週期 m−b。最長真邊界因此給出最小正週期 m−π[m−1]。週期不必整除 m:ababa 長度 5,仍有週期 2。空模式須另行處理:每個文字邊界都是匹配,故即使沒有字元比較,仍有 n+1 個輸出。
為何真正後綴的檢查不足以驗證匹配後歸零?
空前綴永遠是真正後綴。因此歸零能通過相等檢查,卻可能丟掉較長的可用後綴,遺漏重疊出現。字元之間的最長狀態檢查能揭示這種損失;完成後的報告也會與所有真正匹配的視窗核對。
固定例子的字元均為小寫 ASCII,索引由零開始。每個延伸、回退或拒絕事件計一次邏輯字元比較;報告及重設不計比較。診斷子字串檢查和真正匹配清單只是教學用核對,不計入演算法比較數。空模式的全部邊界輸出合併為一個顯示事件,不表示 n+1 次輸出只需常數工作。刻意錯誤的規則只是示範,不是其他正確演算法。
限制總工作量,不是每個字元的工作量
一個字元可能觸發多次回退,並不表示整個算法是二次時間。
定理 9.1.7
(KMP 的總工作量是線性的)
在符號比較為常數時間的假設下,前綴預處理需時 ,文字掃描需時 ,所以搜尋總時間為 ,再加上輸出 個匹配的 。
證明
(以增加額度抵銷每次減少)
建立前綴表時,每次外層迭代最多把匹配長度增加一。每次回退至少減少一,且長度不會負。由零開始,全部回退次數不超過全部增加次數,後者至多為模式長度。
掃描文字也一樣:每個文字字元最多令 增加一次,不匹配回退及完整匹配後的重設只會減少。因此,全部不匹配迴圈迭代只有線性多次。除此以外,每次外層迭代只作常數次比較。
若符號比較為常數時間,前處理需 ,搜尋需 。傳回 個出現另需 輸出工作與空間;前綴表佔 工作空間,匹配清單是額外輸出空間。包括空模式也最多有 個起點,所以總時間為 。
證明透視
為每次回退付款的勢能
把 當作勢能。它從 開始、永不為負,每次外層迭代至多增加 。回退把 換成 ,而 ,因為真前後綴比它所在的字串短,所以每次回退至少使 減少 。因此回退次數至多等於總增加量:掃描中至多 次,預處理中至多 次。這個界是攤銷的:單個字元可能觸發許多次回退,但那是在先前的字元把 推到那麼高之後。
常見錯誤
(線性時間不等於每個字元只比較一次)
這不表示每個文字字元只比較一次。文字索引不往回移,但當前字元可以與多個模式位置比較;線性的保證來自總量分析。
包含空模式的完整實作
約定空模式出現在每個文字邊界,包括首字元之前及末字元之後,共有 個位置。單獨處理此情況,也避免對空模式作索引。
def prefix_function(pattern):
pi = [0] * len(pattern)
for i in range(1, len(pattern)):
j = pi[i - 1]
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
def kmp_find_all(text, pattern):
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
matches = []
j = 0
for i, symbol in enumerate(text):
while j > 0 and symbol != pattern[j]:
j = pi[j - 1]
if symbol == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - len(pattern) + 1)
j = pi[j - 1]
return matches
完整匹配後,下一次迭代前已重設 ,因此比較時 pattern[j] 不會越界。模式比文字長時,掃描自然無法達到完整長度。此實作也不需要額外分隔符或串接模式與文字。
常見錯誤
(用 而不是 回退)
在狀態 失配後,已匹配的字串是 P[:j],其最長真前後綴的長度是 。 屬於較長的前綴 P[:j+1],而它包含剛剛失配的字元。對模式 ababc 和文字 abababc,正確的掃描在讀入 abab 後到達 ,遇到 a 失配,回退到 ,並報告位置 的出現。若用 ,就丟掉前後綴 ab,漏掉這個出現。
最長前後綴也決定最小週期
定義 9.1.8
(字串的週期)
非空字串 長度為 。若正整數 滿足每個 都有 ,稱 為週期。長度 的前後綴,恰好表示首 字元等於末 字元,也就是 的週期條件。
定理 9.1.9
(由最長前後綴得出最小週期)
對長度為 的非空字串 , 的最小正週期為
證明
(週期與前後綴一一對應)
由上述對應, 本身就是一個週期。任何其他週期 都產生長度 的前後綴,不會比最長者長,故 。
週期不必整除長度:ababa 長五,週期仍為二。若週期整除 ,字串就是其首段週期長度區塊的完整重複;例如 ababab 是三次 ab。
例題 9.1.10
(最小週期,包括沒有前後綴的字串)
對 abcabcab,前綴表為 ,故 ,:這個字串是區塊 abc 的重複,並以不完整的區塊 ab 結尾。對 abc,表為 ,:它沒有非空的真前後綴,所以唯一的週期就是整個字串的長度。對 aaaa,表為 ,。
練習與詳解
快速檢查
(1. 找出真正的真前後綴)
列出 ababa 全部真前後綴長度,包括零。為何二、四、五不算?
解答 · 解答 1
長度為零、一、三,非空者是 a、aba。長二前綴 ab 不等於後綴 ba;長四前綴 abab 不等於後綴 baba。五是全串,違反「真」的要求。
快速檢查
(2. 沿真正的前後綴連結回退)
對 ababaca,處理 c 前的最長匹配前後綴是甚麼?列出回退長度及該索引的最終前綴值。
解答 · 解答 2
前一前綴 ababa 的最長前後綴為 aba,長三。鏈為 。c 不能延長任何狀態,故 。
快速檢查
(3. 保留重疊起點)
在 aaaaa 首次匹配 aaa 後,保留哪個狀態?為甚麼?列出全部起點,並解釋重設零會出甚麼問題。
解答 · 解答 3
保留狀態二,對應 aa。全部起點為零、一、二。重設零丟掉兩個已匹配後綴字元,錯誤掃描的剩餘文字便不足以揭示那些重疊的長三出現。
快速檢查
(4. 診斷錯誤回退狀態)
ababc 與 ababbc 的反例中,為何首次不匹配後的長度三狀態無效?錯誤算法最後報告哪個文字視窗?
解答 · 解答 4
已讀 abab 以 bab 結束,不是模式前綴 aba,所以狀態三不代表真正後綴匹配。錯誤延長最後報告起點一的 babbc,內容不相等,表示這是錯誤接受,不只是搜尋較慢。
快速檢查
(5. 多次失敗,總比較量為何仍線性?)
某個文字字元引起多次回退時,哪個量在減少?先前哪項工作限制整次掃描的總回退次數?
解答 · 解答 5
每次回退令匹配前綴長度 嚴格減少。它從零開始、永不負,而且每個文字字元最多令它增加一次。所以全部減少只有先前增加所提供的線性額度。再加每個字元的常數比較,總搜尋時間仍線性。
快速檢查
(6. 求週期,不先假設整除)
用最長前後綴公式,求 ababab 及 ababa 的最小週期。哪個是整數次 ab?為何另一個仍符合週期定義?
解答 · 解答 6
兩者最長前後綴長度為四及三,所以最小週期都是二。ababab 長六,是三次 ab;ababa 長五,但每個索引至少二的字元,仍與前兩格相同。週期定義容許最後只有部分區塊。