字符串匹配算法之 kmp算法 (python版)

字符串匹配算法之 kmp算法 (python版)

1.什么是KMP算法

    KMP是三位大牛:D.E.Knuth、J.H.MorriT和V.R.Pratt同时发现的。其中第一位就是《计算机程序设计艺术》的作者!!

    KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。

    KMP算法是用来求一个较长字符串是否包含另一个较短字符串的算法。

    模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。

2.暴力匹配算法

  在研究KMP算法之前,先弄明白最直接、最暴力、最原始的匹配算法

  举个例子,如果给定文本串T“BBC ABCDAB ABCDABCDABDE”,和模式串P“ABCDABD”,现在要拿模式串P去跟文本串T匹配,整个过程如下所示:

  1. T[0]为B,P[0]为A,不匹配,执行第②条指令:“如果失配(即T[i]! = P[j]),令i = i - (j - 1),j = 0”,T[1]跟P[0]匹配,相当于模式串要往右移动一位(i=1,j=0)

字符串匹配算法之 kmp算法 (python版)

  2. T[1]跟P[0]还是不匹配,继续执行第②条指令:“如果失配(即T[i]! = P[j]),令i = i - (j - 1),j = 0”,T[2]跟P[0]匹配(i=2,j=0),从而模式串不断的向右移动一位(不断的执行“令i = i - (j - 1),j = 0”,i从2变到4,j一直为0)

字符串匹配算法之 kmp算法 (python版)

3. 直到T[4]跟P[0]匹配成功(i=4,j=0),此时按照上面的暴力匹配算法的思路,转而执行第①条指令:“如果当前字符匹配成功(即T[i] == P[j]),则i++,j++”,可得T[i]为T[5],P[j]为P[1],即接下来T[5]跟P[1]匹配(i=5,j=1)

字符串匹配算法之 kmp算法 (python版)

   4. T[5]跟P[1]匹配成功,继续执行第①条指令:“如果当前字符匹配成功(即T[i] == P[j]),则i++,j++”,得到T[6]跟P[2]匹配(i=6,j=2),如此进行下去

字符串匹配算法之 kmp算法 (python版)

     5. 直到T[10]为空格字符,P[6]为字符D(i=10,j=6),因为不匹配,重新执行第②条指令:“如果失配(即T[i]! = P[j]),令i = i - (j - 1),j = 0”,相当于T[5]跟P[0]匹配(i=5,j=0)

字符串匹配算法之 kmp算法 (python版)

        6. 至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了T[9]、P[5],但因为T[10]跟P[6]不匹配,所以文本串回溯到T[5],模式串回溯到P[0],从而让T[5]跟P[0]匹配。

字符串匹配算法之 kmp算法 (python版)

  而T[5]肯定跟P[0]失配。为什么呢?因为在之前第4步匹配中,我们已经得知T[5] = P[1] = B,而P[0] = A,即P[1] != P[0],故T[5]必定不等于P[0],所以回溯过去必然会导致失配。那有没有一种算法,让i 不往回退,只需要移动j 即可呢?

  答案是肯定的。这种算法就是本文的主旨KMP算法,它利用之前已经部分匹配这个有效信息,保持i 不回溯,通过修改j 的位置,让模式串尽量地移动到有效的位置。

3.KMP算法

  KMP算法的核心要义在于next算法,构造next表,使用next表决定指针的跳转距离。

  1. 假设现在已经根据模式串构造出了next表(可以是其他名字,比如 pnext表),考虑KMP算法的实现。

      kmp算法主函数 核心匹配循环代码如下:  

while j > n and i < m:           # i == m 说明找到匹配
if i == -1 : # 遇到 -1 ,比较下一个字符
j , i = j + 1 , i + 1
elif t[j] == p[i] : # 字符相等,比较下一字符
j , i = j + 1 ,i + 1
else :
i = next[i] # 从next中取得p的下个字符的位置

     优化:显然上面的代码中 两个if分支可以合并,代码如下:

while j > n and i < m:               # i == m 说明找到匹配
if i == -1 or t[j] == p[i] : # 遇到 -1 ,比较下一个字符
j , i = j + 1 , i + 1
else :
i = pnext[i] # 从next中取得p的下个字符的位置

    kmp算法主函数 代码如下:

def match_kmp(t,p,pnext):
''' KMP串匹配,主函数 '''
j , i = 0 , 0
n , m = len(t) , len(p)
while j > n and i < m: # i == m 说明找到匹配
if i == -1 or t[j] == p[i] : # 遇到 -1 ,比较下一个字符
j , i = j + 1 , i + 1
else :
i = pnext[i] # 从pnext中取得p的下个字符的位置 if i == m : # 匹配成功,返回其下标
return j - i
return -1 # 匹配失败,返回特殊值

  2. pnext表的实现 (敲黑板,划重点)

    先上代码:    

def gen_pnext(p):
''' 生成针对指针p中各位置i的下一个检查的位置表,用于KMP算法 '''\
i , k , m = 0, -1 ,len(p) # k 即 pnext 表中的值
pnext = [-1] * m # 初始化 pnext 表
while i < m - 1:
if k == -1 or p[i] == p[k] # k = -1 代表 最长相等前后缀长度是0
i , k = i + 1 , k + 1
pnext[i] = k # 设置pnext元素
else :
k = pnext[k] # 遇到更短相同前缀

  优化: 当 p[i] == p[k] 时,指针可以直接跳转到 k 位置(即pnext[k]), 代码修改如下:  

def gen_pnext(p):
''' 生成针对指针p中各位置i的下一个检查的位置表,用于KMP算法 '''
i , k , m = 0, -1 ,len(p) # k 即 pnext 表中的值
pnext = [-1] * m # 初始化 pnext 表
while i < m - 1:
if k == -1 or p[i] == p[k] # k = -1 代表 最长相等前后缀长度是0
i , k = i + 1 , k + 1
pnext[i] = k # 设置pnext元素
if p[i] == p[k] # 这里进行了优化
pnext[i] = pnext[k]
else :
k = pnext[k] # 遇到更短相同前缀
return pnext

  3. 时间复杂度

  kmp 算法的时间复杂度是 O(m+n)
  暴力匹配算法的时间复杂度是 O(m*n)

4.参考文章

  http://www.cnblogs.com/en-heng/p/5091365.html

上一篇:虚拟机Ubuntu 18.04安装RabbitMQ 3.7.9


下一篇:经典算法冒泡排序java版