前言
下面我将按这个目录来介绍 KMP 算法:
- 字符串『前綴』|『後綴』
- PMT(Partial Match Table)『最長公共前後綴』
- Next 表
- KMP 算法描述
- KMP 程式
一、字符串『前綴』|『後綴』
KPM 其實是一種字符串匹配的算法,也就是說檢索字符串,那麼在學習它之前先了解一下『前綴』和『後綴』這 2 個概念。
1. 字符串『前綴』
a. 简单的解释
聲明 2 個字符串: A 和 B
定義它們的關係: A = BS
(S 为任意的非空字符)
那麼就稱: B 是 A 的前缀
b. 舉例來看
現在有一個字符串:Hello
那麼它的前綴有:H, He, Hel, Hell
那麼把這個結果更結構化的表達一下:
"Hello" = { "H", "He", "Hel", "Hell" }
{}
這裡我們稱它為集合
=> 字符串前綴集合
2. 字符串『后綴』
a. 简单的解释
聲明 2 個字符串: A 和 B
定義它們的關係: A = SB
(S 为任意的非空字符)
那麼就稱: B 是 A 的后缀
b. 舉例來看
現在有一個字符串:Hello
那麼它的后綴有:ello, llo, lo, o
那麼把這個結果更結構化的表達一下:
"Hello" = { "ello", "llo", "lo", "o" }
{}
這裡我們稱它為集合
=> 字符串后綴集合
其实这个概念还是挺简单的,我这里参考的是知乎的一个回答来解释一些概念,也许不严谨,但是我认为是易懂的。
不過按我查詢資料來理解 KMP 的時候,有外鏈最先不要跳躍出去,這樣保持一個思維來理解。
接下來將再看一個概念『最長公共前綴』,這個概念才是真正我們編程的時候需要尋找的部分。
二、PMT(Partial Match Table)『最長公共前後綴』
a. 解释和推导
這個概念用文字其實不是那麼好理解,如果硬要用漢字理解的話,就用拆字的方式:最長、公共、前綴、後綴,就是首先要找前綴和後綴,並且要是公共的,並且公共字符串的長度要是最長。
其實我覺得這個漢字解釋是錯的,既然那麼不好解釋,我們就用數學的方式來解釋看看,比較代數式的抽象度更高,更容易看懂。
前提:有一個字符串 \( P_j \)
目的:查找 \( P_j \) 中最長且相等的 k 前缀和 k 後綴
即:滿足條件的最大 k 值,使得,
\( P_0P_1P_2...P_{k-1}P_k = P_{j-k}P_{j-k+1}...P_{j-2}P_{j-1}P{j} \)
这样解释应该比较清晰了,当然这个东西也不是我自己写的,来自于算法老师 July CSDN 中的推导简化的。
b. 实例
模式串: abaabcaba
字符串 | 前綴 | 後綴 | 最长公共字符串 | 最長公共字符串長度 |
---|---|---|---|---|
a | 空 | 空 | 空 | 0 |
ab | a | b | 空 | 0 |
aba | ab | ba | a | 1 |
abaab | abaa | baab | ab | 2 |
abaabc | abaab | baabc | 空 | 0 |
abaabca | abaabc | baabca | a | 1 |
abaabcab | abaabca | baabcab | ab | 2 |
abaabcaba | abaabcab | baabcaba | aba | 3 |
根据上面的分析表,得出最终的表:
模式串 | a | b | a | a | b | c | a | b | a |
---|---|---|---|---|---|---|---|---|---|
最大前缀后缀公共元素长度 | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 |
c. 为什么需要 PMT?
看完這裡應該有個疑問:為什麼是這個步驟找出這樣一張表出來?這個就需要先了解一下由 PMT 表產生的 Next 表。下面我們先來看看 Next 表的相關東西。
三、Next 表
Next 表是由 PMT 表得到的,做到就是將 PMT 表中的每一個值向后移动 1 位,第一位賦值為 -1,為什麼是這樣得到 Next 表呢?接著看下去吧。
先按結論補充一下之前的表格,添加 Next 表
模式串 | a | b | a | a | b | c | a | b | a |
---|---|---|---|---|---|---|---|---|---|
最大前缀后缀公共元素长度 | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 |
Next | -1 | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 |
下面這張圖能很好的解釋為什麼我們需要 PMT 得到的 Next 表,這個表意味著我們能夠跳過一些不必要的字符,通過推斷的結構根據 Next 表的數據跳到已經確定的下一個比較位置,這里的 k
就是最長公共子綴的位置。

當我們在進行比較的時候,其實最後的『失配字符』(匹配失敗的字符)是 \( P_k \),所以真正相同的字符串是 \( P_0P_1...P_{k-1} \),那么我们能得到下面这个公式:
模式串向右移動的位數 := 已匹配字符數 - 失配字符的上一位字符所對應的最大長度值
模式串向右移動的位數 := j - next[j]
这个公式的解释依然出自于 July 的 CSDN 博客 。
以下是文字版公式:
\( S_0S_1 \qquad\qquad\qquad\qquad S_{i-k}S_{i-k+1}...S_{i-1} \quad S_i \\\)
\( \qquad P_0P_1...P_{k-1}P_k...P_{j-k}P_{j-k+1}...P_{j-1} \quad P_j \\\)
\( \qquad\qquad\qquad\qquad\qquad P_0 \quad P_1 \quad\ ...P_{k-1} \quad\ P_kP_{j-k}P_{j-k+1}...P_{j-1}P_j \)
這裡就能看出 KMP 的优势的,比如暴力的字符串匹配过程是需要每个字符都循环遍历进行比较的,如果遇到不匹配的时候总是移动一位然后再进行比较的过程。而 KMP 是可以跳跃一些不必要的匹配步骤的,时间就节约在这个地方,等會兒後面會分析一下最差情況的時間複雜度。
那么这里描述一下暴力匹配字符串的过程,有這麼 2 個字符串:
匹配串T: ababababab abaabcaba
模式串P: abaabcaba

這個很簡單,直接上代碼吧~因為要對比理解才能看出 KMP 節約的地方:
def index(source_string, type_string, pos):
i = pos
j = 0
while i <= len(source_string) - 1 and j <= len(type_string) - 1:
if source_string[i] == type_string[j]:
i += 1
j += 1
else:
i = i - j + 1
j = 0
if j == len(type_string):
return i - len(type_string)
else:
return -1
" output: 8 "
print index('abababababca', 'abca', 0)
這個代碼也是參考的博客,python
的程式很直觀,就不翻譯成 JavaScript
了。
四、KMP 算法描述
上面的準備工作已經差不多了,現在我們根據上面的 Next 表來描述一下算法過程:
- 如果 j = -1, 或者當前字符匹配成功(即S[i] == P[j]),都令 i++, j++,继续依次进行比较;
- 如果 j != -1, 且当前字符匹配失败(即S[i] != P[j]),令 i 不变,j = Next[j]。这个时候就要涉及到按照之前的公式进行移动,移动的位数为:j - Next[j]。
从上面的过程可以看出,我们算法是在解决 \( P_j \) 失配时候的问题。那麼這裡就是我們推斷算法複雜度的地方,算法最差的情況是模式串(P)在 i - j
的位置匹配完成,那么按匹配串(S)來看複雜度就是 O(n),如果算上 Next 表的過程 O(m),最後整體的算法複雜度為:O(n+m)。
五、KMP 程式
經過前面那麼多文字和公式的鋪墊,其實實現最後的程式并不複雜,程式包括 2 部分:
- 總的 KMP 算法實現過程
- Next 表的收集
Next 表的收集是有優化的地方的,優化點將以後再分享,這裡先實現它。
下面的 i
表示後綴索引,j
表示前綴索引。
def get_next_table(P):
i = 0
j = -1
next_table = [-1]
while i < len(P) - 1:
if j == -1 or P[i] == P[j]:
i += 1
j += 1
next_table.insert(i, j)
else:
j = next_table[j]
return next_table
def index_kmp(S, P, pos):
next_table = get_next_table(P)
print next_table
i = pos
j = 0
while i <= len(S) -1 and j <= len(P) - 1:
if j == -1 or S[i] == P[j]:
i += 1
j += 1
else:
j = next_table[j]
if j == len(P):
return i - j
else:
return -1
"""
next_table: [-1, 0, 0, 1, 2, 3, 4, 0]
return: 2
"""
print index_kmp('ababababca', 'abababca', 0)
這裡的程式也是參考的網上的一篇文章
参考的太多了,贴一些列表吧:
- algorithmen-kmpen
- 从头到尾彻底理解KMP
- 从有限状态机的角度去理解Knuth-Morris-Pratt Algorithm(又叫KMP算法)
- 字符串的匹配模式算法
- 如何更好的理解和掌握 KMP 算法
- Matrix67-KMP算法详解
這篇先這樣吧,之後再寫一些優化和自動機相關的內容呢。