BM算法的实现

这是我参与8月更文挑战的第5天，活动详情查看：8月更文挑战

我们在BM算法学习了BM算法的原理，今天我们来看一下代码如何实现。

我们接下来来看BM算法的代码是如何实现的。

  "坏字符规则"中当遇到坏字符时，我们要计算后移的位数Ai-Bi，其中Bi的计算的重点。如果我们拿坏字符在模式串中顺序查找，这样是可以实现，不过效率比较低下。我们可以用大小256的数组，来记录每个字符在模式串中出现的位置。数组的下标对应的是字符的Ascii编码，数组中存储的是这个字符在模式串中的位置。

SIZE = 256
def generateBC(b, m):
    bc=[-1]*SIZE
    for i in range(m):
        accii=ord(b[i])
        bc[accii]=i
    return b

        我们先把BM算法中的“坏字符规则”写好，先不考虑“好后缀规则”，并且忽略掉Ai-Bi为负数的情况。

def bm(a,n,b,m):
     #生成bc散列表
     bc=generateBC(b,m)
     #i表示主串与模式串对齐的第一个字符
     i = 0
     while i<=n-m:
          for j in range(m-1,-2,-1): #模式串从后往前匹配
               if(a[i+j]!=b[j]): #坏字符对应模式串中的下标是j
                    break
​
          if(j<0):
               #表示匹配成功
               return i
          #Ai-Bi,等同于向后滑动几位
          i = i + (j - bc[ord(a[i+j])])
     return -1

到目前为止，我们已经实现了“坏字符规则”的代码框架，剩下就是需要往里面添加“好后缀规则”的代码逻辑了。`在继续讲解之前，我们先简单回顾一下，前面讲的“好后缀规则”中最关键的内容。

• 在模式串中，查找和好后缀匹配的另一个子串。
• 在好后缀的后缀子串中，查找最长的，能跟模式串前缀子串相匹配的后缀子串。

      我们可以这么考虑，因为好后缀也是模式串的后缀子串，所以，我们可以在模式串和主串进行匹配之前，通过预处理模式串，预先计算好模式串中的每个后缀子串，对应的另外一个可匹配子串中的位置。这个预处理过程有点复杂。大家可以多读几遍，在纸上画一画。

     我们先来看如何表示模式串中的不同后缀子串呢？因为后缀子串的最后一个字符的位置是固定的，下标为m-1，所以我们只需要记录长度就可以了。通过长度，我们可以唯一确定一个后缀子串。

      下面我们引入一个关键的数组suffix。suffix数组的下标k，表示后缀子串的长度，数组对应的位置存储的是，在模式串中和好后缀{u}相匹配的子串{u*}的起始下标位置。

      其中有一个点需要注意，如果模式串中有多个子串跟后缀子串相匹配，我们选最靠后的那个子串的起始位置，以免滑动的太远，错过可能匹配的情况。

    接下来我们来看好后缀规则的第二条，就是要在好后缀的后缀子串中，查找最长的能跟模式串前缀子串匹配的后缀子串。接来下，我们来引入另一个数组变量prefix，来记录模式串的后缀子串是否能匹配模式串的前缀子串。

 

    接下来我们来看如何给这两个数组赋值呢？我们拿下标为0~i的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。我们来看代码实现。

def generateSP(b,m):
     suffix= [-1]*m
     prefix= [False]*m
     for i in range(m-1):
          j=i
          k=0 #公共后缀子串长度
          while (j>=0 and b[j]==b[m-1-k]):
               j=j-1
               k=k+1
               #j+1表示公共后缀子串在b[0, i]中的起始下标
               suffix[k]=j+1
​
          if (j==-1):
               #如果公共后缀子串也是模式串的前缀子串
               prefix[k] = True
​
     return suffix,prefix

　下面我们来看如何根据好后缀规则，来计算模式串往后滑动的位数？假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k]不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k]等于 -1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们就用下面这条规则来处理。好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k]等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位。如果两条规则都没有找到可以匹配的好后缀及其后缀子串的后缀子串，我们就将整个模式串后移 m 位。到此为止，我们的好后缀规则也聊完了，我们现在把好后缀规则的代码插入到前面的框架中，就可以得到完整版本的BM算法了。`

#散列表的大小
SIZE = 256
def generateBC(b, m):
    bc=[-1]*SIZE
    for i in range(m):
        accii=ord(b[i])
        bc[accii]=i
​
    return bc
​
def generateSP(b,m):
     suffix= [-1]*m
     prefix= [False]*m
     for i in range(m-1):
          j=i
          k=0 #公共后缀子串长度
          while (j>=0 and b[j]==b[m-1-k]):
               j=j-1
               k=k+1
               #j+1表示公共后缀子串在b[0, i]中的起始下标
               suffix[k]=j+1
​
          if (j==-1):
               #如果公共后缀子串也是模式串的前缀子串
               prefix[k] = True
​
     return suffix,prefix
​
#j表示坏字符对应的模式串中的字符下标
#m表示模式串长度
def moveSP(j,m,suffix,prefix):
     #好后缀的长度
     k=m-1-j
     if suffix[k]!=-1:
          return j-suffix[k]+1
     for r in range(j+2,m):
          if prefix[m-r]==True:
               return r
     return m
​
def bm(a,n,b,m):
     #生成bc散列表
     bc=generateBC(b,m)
     suffix, prefix = generateSP(b,m)
     #i表示主串与模式串对齐的第一个字符
     i = 0
     while i<=n-m:
          for j in range(m-1,-2,-1): #模式串从后往前匹配
               if(a[i+j]!=b[j]): #坏字符对应模式串中的下标是j
                    break
​
          if(j<0):
               #表示匹配成功
               return i
          #Ai-Bi,等同于先后滑动几位
          x = j - bc[ord(a[i+j])]
          y = 0
          #如果有好后缀的话
          if j < m-1:
             y = moveSP(j, m, suffix, prefix)
​
          i = i + max(x, y)
     return -1

到此为止，我们的BM算法就聊完。

如果想要本文的pdf版本，可以关注公众号“程序员学长”私信我。

   更多硬核知识。请关注公众号“程序员学长”。