KMP算法

kmp算法与有限自动机的思想是一致的,都是尽量减少匹配失败后的回溯,而是直接进行目标串接下来的匹配。自动机使用了匹配失败时目标串的当前字符,而kmp没有使用,这就是为什么kmp的预处理时间比自动机要少的原因。下面这个图形象说明了,如何来减少回溯。总之,还是那句话,充分利用已经匹配的信息。因为已经匹配的信息,就是匹配串自己的一部分,而匹配串是可以预处理的。

 

kmp

与自动机的一样,我们如果分析出图中匹配串M已匹配部分,即图示中的蓝色部分:最大相同后缀M[i...j]与前缀M[1...n],那么失败字符X,接下直接和M[n+1],即Z进行比较即可。注:最大后缀与其相同的前缀用红色块表示

换句话说,我们要分析匹配串自身的信息,然后得出每个字符失败后,其接下来要进行匹配的字符是哪个。例如上图中Y失败后,接下来应当与Z进行比较,因为Z前面的部分无需再次进行比较处理。

如何分析一个串自身这种信息呢?

假设P[i]表示:M[i]失败后,应当与M[P[i]]进行比较,即传说中的next。
现在我们知道P[k],如何得知P[k+1]呢?
如果M[k]和M[P[k]]相等的话,那么红色部分不就又增长了一个格,即P[k+1]=P[k]+1
如果M[k]和M[P[k]]不相等的话,那么红色部分不仅不能增长,有可能会缩短,因为必须找一个最大相同前缀与后缀M[1..j-1]与M[...k-1]且M[j]==M[k],即P[k]==j+1,注意此时M[j]==M[k]。换句话说,就是说将M[k]作为后缀的尾字符,找其对应的相同最大前缀。注意,靠近M[k]的小红色部分与靠近M[P[k]]的‘小红色部分’(虽然没有表出,但它是存在的)是相同的。那么找如下图所示的小红色块前缀且紧跟其的字符M[j]与M[k]相等的位置,即可:

 

kmp_next

换句话说,就是找M[P[k]]的next,即P[P[M[k]]],且M[P[P[M[k]]]+1]==M[k],要不行,则继续递归向前,直到满足上面的条件。

 

代码如下:

  1 #!/usr/bin/env python
  2 # -*- coding=utf-8 -*-
  3
  4 """
  5     Author : yangxiaowei
  6     Function:String search algorithm completion
  7 """
  8
  9 class KMP:
 10
 11     def __init__(self, str):
 12         self.pattern = str
 13         if self.pattern:
 14             self.kmp_prepare()
 15
 16
 17     def kmp_prepare(self):
 18         self.kmp_next = []
 19         if not self.pattern:return
 20
 21         self.kmp_next.append(-1)
 22         self.kmp_next.append(0)
 23         pattern_len = len(self.pattern)
 24         #know N[i-1],find N[i]
 25         for i in range(2,pattern_len):
 26             self.kmp_next.append(0)
 27             k = self.kmp_next[i-1]
 28             #if P[i-1]==P[N[i-1]],N[i]=N[i-1]+1
 29             if self.pattern[i-1] == self.pattern[k]:
 30                 self.kmp_next[i] = self.kmp_next[i-1] +1
 31             #if P[i-1]!=P[N[i-1]],find pre-pattern
 32             else:
 33                 k = self.kmp_next[k]
 34                 while k >= 0:
 35                     if self.pattern[i-1] == self.pattern[k]:
 36                         self.kmp_next[i] = k+1
 37                         break
 38                     k = self.kmp_next[k]
 39
 40     def search(self,content):
 41         result = []
 42         if not self.pattern:return result
 43         i = 0
 44         j = 0
 45         l = len(content)
 46         while j!=l:
 47             if i==-1:
 48                 j += 1
 49                 i = 0
 50                 continue
 51             char = content[j]
 52             if char==self.pattern[i]:
 53                 i+=1
 54                 j+=1
 55                 if i==len(self.pattern):
 56                     result.append((self.pattern,j-i-1,len(self.pattern)))
 57                     i = 0
 58             else:
 59                 i = self.kmp_next[i]
 60         return result
 61
 62     def print_search(self,result,content):
 63         for p,i,l in result:
 64             print content[:i+1],
 65             print p,
 66             print content[i+l+1:]
 67
 68
 69
 70 if __name__ == "__main__":
 71     content = "xabdabdabdabcefabcabdabc"
 72     kmp = KMP("bd")
 73     r = kmp.search(content)
 74     kmp.print_search(r,content)

发表评论