快捷導(dǎo)航

KMP算法精解及其Python版的代碼示例

更新時(shí)間：2016年06月01日 18:51:33 作者：WhiteFish

KMP算法基本上被人們用作字符串的匹配操作,這里我們就來(lái)介紹KMP算法精解及其Python版的代碼示例,需要的朋友可以參考下

KMP算法是經(jīng)典的字符串匹配算法，解決從字符串S，查找模式字符串M的問(wèn)題。算法名稱來(lái)源于發(fā)明者Knuth，Morris，Pratt。
假定從字符串S中查找M，S的長(zhǎng)度ls，M的長(zhǎng)度lm，且（ls > lm）。

樸素的字符串查找方法
從字符串S的第一個(gè)字符開(kāi)始與M進(jìn)行比較，如果匹配失敗。從下一字符開(kāi)始，重新比較。指導(dǎo)第 (ls - lm) 個(gè)字符。
這種方法容易想到并且容易理解，效率不高。
問(wèn)題在于每次匹配失敗后，移動(dòng)的步伐固定為 1，其實(shí)步子可以邁得再大一些。

KMP的字符串查找方法
假定在模式串的連續(xù)字串M[0, i] 且 i < lm，已經(jīng)成功匹配字符串S。但是不巧第 i+1 個(gè)字符失敗了，怎么辦？移動(dòng)一個(gè)字符，重頭再來(lái)？當(dāng)然不好，那就是樸素路線了。我們能否從跌倒的地方繼續(xù)走呢？
既然字串M[0 - i]已經(jīng)匹配成功，那就從這個(gè)子串上做文章。舉個(gè)栗子

S序號(hào)	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序號(hào)	0	1	2	3	4	5

此時(shí)匹配失敗在M串的第5個(gè)字符，前4個(gè)字符已經(jīng)匹配成功。
如果從跌倒的地方出發(fā)，則需要存在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不存在，那就老老實(shí)實(shí)的樸素了。
從上面的表格可以直觀的看出，下一次匹配只要把M串移動(dòng)到 j + 3 位置，從 j+5 開(kāi)始匹配就可以。很容易看出來(lái) 在已經(jīng)匹配成功的字串M[0 , 4]中有最長(zhǎng)的子串（M[0 , 1] == M[3 , 4]），這個(gè)就是問(wèn)題的關(guān)鍵。
因此KMP的核心部分就是計(jì)算模式串的各個(gè)子串的 k。

實(shí)例
首先我們來(lái)看一下字符串的樸素匹配.
可以想象成把文本串s固定住,模式串p從s最左邊開(kāi)始對(duì)齊,如果對(duì)齊的部分完全一樣,則匹配成功,失敗則將模式串p整體往右移1位,繼續(xù)檢查對(duì)齊部分,如此反復(fù).

#樸素匹配 
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

關(guān)于kmp算法,講的最好的當(dāng)屬阮一峰的<字符串匹配的KMP算法>.一路讀下來(lái),豁然開(kāi)朗.
其實(shí)就是,對(duì)模式串p進(jìn)行預(yù)處理,得到前后綴的部分匹配表,使得我們可以借助已知信息,算出可以右移多少位.即 kmp = 樸素匹配 + 移動(dòng)多位.
更多細(xì)節(jié)請(qǐng)看阮一峰的文章,這里就不展開(kāi)了.
下面給出python的代碼實(shí)現(xiàn).

#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位往右移,可以一次移動(dòng)多位 
    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")

您可能感興趣的文章: