Boyer-Moore字符串搜索（BM算法）的Python实现

 1 def my_BM(t,p):
 2     ‘‘‘bm算法的自我实现，在t串中匹配p串，从模式串的尾部开始匹配‘‘‘
 3     ‘‘‘需要坏字符数组badchar[]和好后缀数组goodsuffix[]
 4     每次失配后，根据两判据中最大的值移动p串，比较指针移动至最后‘‘‘
 5     BadChar=BClist(p)
 6     GoodSuffix=GSlist(p)
 7     tlen,plen=len(t),len(p)
 8     if tlen<plen:
 9         return -1
10     i,k=plen-1,plen-1   #从p串尾部开始比较
11     move=0
12     while i<tlen and k>=0:
13         if t[i]==p[k]:
14             i,k=i-1,k-1
15         else:
16             BCmove=k-BadChar[ord(t[i])] if BadChar[ord(t[i])]!=-1  else plen
17             move=max(GoodSuffix[k],BCmove)   #滑动位数
18             i,k=i+move+plen-1-k,plen-1
19     if k<=0:
20         return i+1
21     return -1
22             
23 
24 def BClist(p):
25     ‘‘‘产生坏字符的失配移动表
26    j处失配，p串整体右移j-bc[T[j]]位‘‘‘
27     bc=[-1]*128   #标准ACCII表，可显示128个常用字符
28     plen=len(p)
29     for i in range(plen):
30         bc[ord(p[i])]=i  #利用ord--chr函数的互相转化，间接直接将字符作为下标
31     return bc
32 
33 def GSlist(p):
34     ‘‘‘产生好后缀方法的失配移动表，若i处失配，则分三种：相应地跳过字符个数逐渐变大
35     1. 已匹配成功的字符串形成的后缀gs，在p串中x存在相等的子串，则将p串右移i-x+1；
36     2. 条件1不成立，则在p的前缀中寻找gs的后缀相等的最大串，设后缀头在j，这一步类似于kmp的寻找最大相等前后缀，将p串右移j位；
37     3. 条件1，2都不成立，本轮比较失败，将p串整体移动p长度m‘‘‘
38     plen=len(p)
39     GS=[plen]*plen  #初始化数组，并直接置于条件3的值
40     GS[plen-1]=1   #好后缀规则可以单独使用，它是基于已匹配的字符进行优化跳过，若首次匹配就失败，则应该只移动p串一位
41     for i in range(plen-1):    #i处失配 
42         #条件2，求i之后的后缀串，其在p串前缀中的最大相等前缀
43         #虽然也是求最大相等前后缀，但与kmp不同，kmp求的是前缀子串中的最大相等前后缀，而好后缀算法中求的是整个p串的最大相等前后缀，只是对该前后缀的长度做了限制
44         k=0
45         j=i+1
46         while j<plen:
47             if p[k]==p[j]:
48                 k,j=k+1,j+1
49             else:
50                 j=j-k+1
51                 k=0
52         if k!=0:
53             GS[i]=plen-1-k
54         #搜寻p串中是否还有与p[i+1:]相等的子串，即条件1
55         substr=find_last(p[:plen-1],p[i+1:])   #find_last(t,p)函数寻找t串中最后一个p串的起始位置，若没有则返回-1
56         if substr!=-1:
57             GS[i]=i-substr+1
58     return GS