KMP算法是經典的字符串匹配算法，解決從字符串S，查找模式字符串M的問題。算法名稱來源于發明者Knuth，Morris，Pratt。
假定從字符串S中查找M，S的長度ls，M的長度lm，且（ls > lm）。
樸素的字符串查找方法
從字符串S的第一個字符開始與M進行比較，如果匹配失敗。從下一字符開始，重新比較。指導第 (ls - lm) 個字符。
這種方法容易想到并且容易理解，效率不高。
問題在于每次匹配失敗后，移動的步伐固定為 1，其實步子可以邁得再大一些。
KMP的字符串查找方法
假定在模式串的連續字串M[0, i] 且 i < lm，已經成功匹配字符串S。但是不巧第 i+1 個字符失敗了，怎么辦？移動一個字符，重頭再來？當然不好，那就是樸素路線了。我們能否從跌倒的地方繼續走呢？
既然字串M[0 - i]已經匹配成功，那就從這個子串上做文章。舉個栗子
| S序號 | j | j + 1 | j + 2 | j + 3 | j + 4 | j + 5 | j+6 | j + 7 | 。。。 |
| S串 | a | b | c | a | b | c | d | e | 。。。 |
| M串 | a | b | c | a | b | d | |||
|
M序號 |
0 | 1 | 2 | 3 | 4 | 5 |
此時匹配失敗在M串的第5個字符，前4個字符已經匹配成功。
如果從跌倒的地方出發，則需要存在M[0, 4]的子串M[0, k] == S[j+4-k , j+4]。
由于M[0, 4] == S[j , j+4] 則有 字串S[j+4-k, j+4] == M[4-k, 4]。綜上有M[0, k] == M[4-k, 4]
如果這樣的k不存在，那就老老實實的樸素了。
從上面的表格可以直觀的看出，下一次匹配只要把M串移動到 j + 3 位置，從 j+5 開始匹配就可以。很容易看出來 在已經匹配成功的字串M[0 , 4]中有最長的子串 （M[0 , 1] == M[3 , 4]），這個就是問題的關鍵。
因此KMP的核心部分就是計算模式串的各個子串的 k。
實例
首先我們來看一下字符串的樸素匹配.
可以想象成把文本串s固定住,模式串p從s最左邊開始對齊,如果對齊的部分完全一樣,則匹配成功,失敗則將模式串p整體往右移1位,繼續檢查對齊部分,如此反復.
|
1
2
3
4
5
6
7
|
#樸素匹配 def naive_match(s, p): m = len(s); n = len(p) for i in range(m-n+1):#起始指針i if s[i:i+n] == p: return True return False |
關于kmp算法,講的最好的當屬阮一峰的<字符串匹配的KMP算法>.一路讀下來,豁然開朗.
其實就是,對模式串p進行預處理,得到前后綴的部分匹配表,使得我們可以借助已知信息,算出可以右移多少位.即 kmp = 樸素匹配 + 移動多位.
更多細節請看阮一峰的文章,這里就不展開了.
下面給出python的代碼實現.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#KMP def kmp_match(s, p): m = len(s); n = len(p) cur = 0#起始指針cur table = partial_table(p) while cur<=m-n: for i in range(n): if s[i+cur]!=p[i]: cur += max(i - table[i-1], 1)#有了部分匹配表,我們不只是單純的1位1位往右移,可以一次移動多位 break else: return True return False #部分匹配表 def partial_table(p): '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]''' prefix = set() postfix = set() ret = [0] for i in range(1,len(p)): prefix.add(p[:i]) postfix = {p[j:i+1] for j in range(1,i+1)} ret.append(len((prefix&postfix or {''}).pop())) return ret print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD") print partial_table("ABCDABD") print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD") |
