檢視 KMP演算法的原始碼

: 佇本文中，會使用因為零的陣列來表示字串。比如講，若字攕 ` S=" ABC " `，著 ` S [二] ` 表示字元 `'C'`。這款表示方法佮 C 語言一致。

佇電腦科學當中，'''Knuth-Morris-Pratt 字串走揣演算法'''（簡稱做'''KMP 演算法'''）會當踮一个字捾 ` S ` 來走揣一个字 ` W ` 出現位置。一个詞在不匹配時本身就包含有夠額的資訊來確定後一个匹配可能的開始位置，此演算法利用這一特性以避免重新檢查進前配對的字元。

這个演算法由高德納佮沃恩 ・ 普拉特在一九七四年構思，仝年詹姆斯 ・ H ・ 莫里斯嘛獨立地設計出這種表演算法，落尾三人佇一九七七年聯合發表。

==走揣過程==

以 ` W `=` " ABCDABD " `，` S `=` " ABC ABCDAB ABCDABCDABDE " ` 為例說明走揣過程。走揣過程同時使用兩个迴圈變數 ` m ` 和 ` i `：

* ` m ` 代表主文字捾 ` S ` 內匹配字串 ` W ` 的當前走揣位，
* ` i ` 代表匹配字串 ` W ` 往過做比較的字元位置。

圖示如下：

` ` `
一二
m : 01234567890123456789012
S : ABC ABCDAB ABCDABCDABDE
W : ABCDABD
i : 十二孵三千四百五十六
` ` `

對 ` W ` 佮 ` S ` 的開頭比較起。比對嘛 ` S [三] (='') ` 時，發現 ` W [三] (='D') ` 佮之不符。接落去並毋是對 ` S [一] ` 比較落去。已經知影 ` S [一] ~ S [三] ` 無與 ` W [零] ` 相合。所以，略過遮的字元，令 ` m=四 ` 以及 ` i=零 `。

` ` `
一二
m : 01234567890123456789012
S : ABC ABCDAB ABCDABCDABDE
W : ABCDABD
i : 十二孵三千四百五十六
` ` `

如上所示，檢核矣 ` " ABCDAB " ` 這字攕。毋過，後一字元便無相合。會當注意著，` " AB " ` 佇咧 ` " ABCDAB " ` 的頭尾處攏有出現。所以意味尾溜的 ` " AB " ` 咱是後改較的起始點。所以，令 ` m=八 , i=二 `，繼續較。圖示如下：

` ` `
一二
m : 01234567890123456789012
S : ABC ABCDAB ABCDABCDABDE
W : ABCDABD
i : 十二孵三千四百五十六
` ` `

佇咧 ` m=十 ` 的所在，閣出現無相符合的情形。類似地，令 ` m=十一 , i=零 ` 繼續較：

` ` `
一二
m : 01234567890123456789012
S : ABC ABCDAB ABCDABCDABDE
W : ABCDABD
i : 十二孵三千四百五十六
` ` `

這陣，` S [十七] (='C') ` 無與 ` W [六] ` 相仝，但是已經配合的部份 ` " ABCDAB " ` 亦為首尾均有 ` " AB " `，採取一貫的做法，令 ` m=十五 ` 和 ` i=二 `，繼續搜揣。

` ` `
一二
m : 01234567890123456789012
S : ABC ABCDAB ABCDABCDABDE
W : ABCDABD
i : 十二孵三千四百五十六
` ` `

揣著完全匹配的字攕矣，其實位置佇佗位 ` S [十五] ` 的所在。

==部份匹配表==

'''部份匹配表'''，閣叫做'''失配函式'''，作用是予演算法無需要濟擺匹配 ` S ` 中的任何字元。會當實現線性時間搜揣的關鍵是佇咧主串的一寡欄位中檢查模式串的 _ 初初彼个欄位 _，會當確切的知影佇咧進前位置進前的一个潛在匹配的位置。嘛會使講，佇袂䆀過任何藏佇匹配的狀況之下，" 預搜揣 " 這个模式串本身並且共翻做一个包含所有可能會失配的位對應會當踅過上濟無效字元的列表。

對於 ` W ` 中的任何位置，攏希望會當查詢彼个位前（無包括彼个位置）有可能的 ` W ` 的上長初初彼个欄位的長度，毋是重新對 ` W [零] ` 開始較整個欄位，這長度就是揣後一个匹配的時陣回退的距離。所以 ` T [i] ` 是 ` W ` 的可能的 _ 適當的 _ 初初的彼个欄位嘛是結束佇 ` W [i-一] ` 的子串的上大長度。予空字串長度是零。做一个失配出這馬模式串的上起先，這是特殊情況（無法度回退）， 設定 ` T [零]=影一 `，佇下跤咧討論。

===建立表演算法範例===

以 ` W=" ABCDABD " ` 做例。以下一个看會著，部份匹配表的生成過程佮前術走揣過程大同小異，而且類似原因是高效的。

首先，設定 ` T [零]=影一 `。為著求出 ` T [一] `，著愛揣著一个 ` " A " ` 有影字尾（正字尾指不等於原串的字尾）兼 ` W ` 的字首。猶毋過 ` " A " ` 無正字尾，所以設定 ` T [一]=零 `。類似地，` T [二]=零 `。

繼續到 ` T [三] `，注意著檢查'''所有'''這个字尾有一个捷徑：假設存佇符合條件的頭前字尾，兩者來分別 ` W [零 . . 一]=W [一 . . 二] `，定著有 ` W [零 . . 零]=W [一 . . 一] `。因為 ` W [零 . . 零] ` 亦是 ` W ` 的真字條，頂一步必然已經得著 ` T [二]=一 `（喔有 ` T [二]=零 `，說明假無成立）。 一般地，遍歷過甲每一字元的時陣，干焦上一步已經發現一个大 m 的有效的字尾，才需要判斷有沒有長為 m + 一的字尾，不需要考慮長為 m + 二、m + 三等的字尾。

對而且，毋免考慮講長二的字尾，唯一需要考慮的長度一亦不可行，故得著 ` T [三]=零 `。

紲落來是 ` W [四]='A'`。是因為仝款理由，需要考慮的上大長度為一，並且佇咧 `'A'` 這个情形中有效，回退到走揣的當前字元 _ 進前 _ 的欄位，所以 ` T [四]=零 `。

這馬考慮後一字元 ` W [五]='B'`，使用按呢的邏輯：若捌發現一个模式佇咧頂一字元 ` W [四] ` 進前出現，繼續到當前字元 ` W [五] `，啊佇伊進前伊本身會擁有一个結束佇 ` W [四] ` 合適合的初步，佮事實顛倒反的是已經揣著 `'A'` 是上早出現佇咧結束 ` W [四] ` 的合適欄位。所以為著欲揣著 ` W [五] ` 的終止串，無需要檢視 ` W [四] `。所以 ` T [五]=一 `。

最後到 ` W [四]='A'`。後一字元是 `'B'`，並且這嘛確實是 ` W [五] `。此外，頂懸的仝款參數說明為著欲走揣 ` W [六] ` 的欄位，毋免去共頭前檢視 ` W [四] `，所以會出 ` T [六]=二 `。

所以表示下跤的：

另外一个閣較複雜佮趣味的例：

===建立表演算法的虛擬碼的解說===

頂頭的例以上少的複雜步驟展示了組織這个表格的一般性方法。按呢做的原理是對整體的搜揣：大多數工課已經咧檢測著彼當陣位置的時陣做了矣，賰需要做甲足少的。略仔複雜的一點是揣著一个共同前字尾。這就是愛有一寡初始化的代碼。

` ` `
'''algorithm'''_ kmp \ _ table _ :
'''input''':
an array of characters , W ( the word to be analyzed )
an array of integers , T ( the table to be filled )
'''output''':
nothing ( but during operation , it populates the table )

'''define variables''':
an integer , pos ← 二 ( the current position we are computing in T )
an integer , cnd ← 零 ( the zero-based index in W of the next
character of the current candidate substring )

( the first few values are fixed but different from what the algorithm
might suggest )
'''let'''T [零] ← 影一 , T [一] ← 零

'''while'''pos < length ( W ) do
( first case : the substring continues )
'''if'''W [pos-一]=W [cnd]'''then'''
'''let'''cnd ← cnd + 一 , T [pos] ← cnd , pos ← pos + 一

( second case : it doesn't , but we can fall back )
'''else''''''if'''cnd > 零'''then'''
'''let'''cnd ← T [cnd]

( third case : we have run out of candidates . Note cnd=零 )
'''else'''
'''let'''T [pos] ← 零 , pos ← pos + 一
` ` `

===建立表的演算法的效率===

建立表的演算法的複雜度是 $ O ( n ) $，其中 $ n $ 是 ` W ` 的長度。

除去一寡初初化的工課，所有的工課攏佇迴箍內底完成。為著說明迴圈執行用矣 $ O ( n ) $ 的時間，考慮 ` pos ` 和 ` pos-cnd ` 的大細。

* 佇第一个分支里，` pos-cnd ` 不變，而且 ` pos ` 佮 ` cnd ` 同時自增，自然，` pos ` 加了。
* 佇第二个分支里，` cnd ` 予閣較細的 ` T [cnd] ` 所替代，自來增加了 ` pos-cnd `。
* 佇第三个分支里，` pos ` 加了，而且 ` cnd ` 不變，所以乎 ` pos ` 和 ` pos-cnd ` 攏有增加喔。

因為乎 ` pos ≥ pos-cnd `，即在每一个階段欲按怎 ` pos ` 加添，欲按怎 ` pos ` 的一个下界增加。故既然演算法佇 ` pos=n ` 時終止，此迴圈必然在上濟 $ 二 n $ 迵天了後終止。所以建立表的演算法的複雜度是 $ O ( n ) $。

==另見==

* Boyer-Moore 字串搜揣演算法

==外部連結==

*（英文）An explanation of the algorithm and sample C + + code by David Eppstein
*（英文）Knuth-Morris-Pratt algorithm description and C code by Christian Charras and Thierry Lecroq
*（英文）Interactive animation for Knuth-Morris-Pratt algorithm by Mike Goodrich
*（英文）Explanation of the algorithm from scratch by FH Flensburg .

==參照==

* 高德納；James H . Morris , Jr , Vaughan Pratt . Fast pattern matching in strings . SIAM Journal on Computing . 一千九百七十七 ,'''六'''( 二 ) : 三百二十三–三仔五 [二千空六五七鋪二十七] .（原始內容存檔佇兩千空一十五一鼻四）.
* Thomas H . Cormen ; Charles E .Leiserson , Ronald L . Rivest , Clifford Stein . Section 三十二孵四 : The Knuth-Morris-Pratt algorithm . Introduction to Algorithms Second edition . MIT Press and McGraw-Hill . 兩千空一 : 九百二十三孵九百三十一 . ISBN 九百七十八追空九二百六十二孵三千二百九十三孵三 .   引文格式的一維護：趁的文字 ( link )

[[分類: 待校正]]