搜尋文字時,常會先匹配模式開頭好幾個字元,卻在下一個字元失敗。若直接由下一個文字位置重新開始,就會丟掉資訊:已匹配部分的某個後綴,可能本來就是有效的模式前綴。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 延長,所以沒有匹配。回退需要子字串相等作理據,不是只要數值變小就可以。
這個互動圖重現下面練習題的方法,包括上面的錯誤匹配例子。若想獨立練習,請先嘗試題目。選擇錯誤匹配示例、搜尋視圖及遞減規則,可查看無效回退。
限制總工作量,不是每個字元的工作量
一個字元可能觸發多次回退,並不表示整個算法是二次時間。
定理 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 長五,但每個索引至少二的字元,仍與前兩格相同。週期定義容許最後只有部分區塊。