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


            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位,继续检查对齐部分,如此反复.





#朴素匹配 

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的代码实现.





#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")