2023年7月20日发(作者：)

字符串匹配BF算法、KMP算法以及BM算法Python实现因为选修了搜索引擎的课程，需要做传统的字符串检索匹配实验。我在⽹上找了很久的Python的源代码，有些是返回的结果不是我想要的，有些则是完全不能运⾏。所以我在这⾥整理了我的学习过程。下⾯我会贴出⼀些⽐较好的算法教程链接以及Python实现。BF算法BF（Brute Force）算法就是朴素的暴⼒匹配。BF算法的基本思想是从主串的start位置开始与模式串进⾏匹配，如果相等，则继续⽐较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进⾏⽐较直⾄模式串的所有字符都已⽐较成功，则匹配成功，或者主串所有的字符已经⽐较完毕，没有找到完全匹配的字串，则匹配失败。Python实现：def BF(s, p): """ 蛮⼒法字符串匹配 """ indies = [] n = len(s) m = len(p) for i in range(n - m + 1): index = i

for j in range(m):

if s[index] == p[j]:

index += 1 else:

break if index - i == m:

(i)

return indiesKMP算法KMP（Knuth-Morris-Pratt）匹配算法是对BF算法的改进。具体过程就是计算⼀张“部分匹配表”来改进移动距离。⽹上有很多教程，我这⾥给⼤家推荐，写的⾮常通俗易懂。Python实现：def getNextList(s): n = len(s) nextList = [0, 0] j = 0 for i in range(1, n): while j > 0 and s[i] != s[j]: j = nextList[j] if s[i] == s[j]: j += 1 (j) return nextListdef KMP(s, p): """ Knuth-Morris-Pratt算法实现字符串查找 """ n = len(s) m = len(p) nextList = getNextList(p) indies = [] j = 0 for i in range(n): while s[i] != p[j] and j > 0: j = nextList[j] if s[i] == p[j]: j += 1 if j == m: (i-m+1) j = nextList[j] return indiesBM算法BM（Boyer-Moore）算法是对KMP进⼀步的改进。总体来说BM算法效率是⾼于KMP算法的，⽂本量越⼤BM算法的效果越明显。BM算法通过两张表来改进移动的距离。我在这⾥还是给⼤家推荐。Python实现：def getBMBC(pattern): #

预⽣成坏字符表 BMBC = dict() for i in range(len(pattern) - 1): char = pattern[i] #

记录坏字符最右位置（不包括模式串最右侧字符） BMBC[char] = i + 1 return BMBCdef getBMGS(pattern): #

预⽣成好后缀表 BMGS = dict() #

⽆后缀仅根据坏字移位符规则 BMGS[''] = 0 for i in range(len(pattern)): #

好后缀 GS = pattern[len(pattern) - i - 1:] for j in range(len(pattern) - i - 1): #

匹配部分 NGS = pattern[j:j + i + 1] #

记录模式串中好后缀最靠右位置（除结尾处） if GS == NGS: BMGS[GS] = len(pattern) - j - i - 1 return BMGSdef BM(string, pattern): """ Boyer-Moore算法实现字符串查找 """ m = len(pattern) n = len(string) i = 0 j = m indies = [] BMBC = getBMBC(pattern=pattern) #

坏字符表 BMGS = getBMGS(pattern=pattern) #

好后缀表 while i < n: while (j > 0): if i + j -1 >= n: #

当⽆法继续向下搜索就返回值 return indies #

主串判断匹配部分 a = string[i + j - 1:i + m] #

模式串判断匹配部分 b = pattern[j - 1:] #

当前位匹配成功则继续匹配 if a == b: j = j - 1 #

当前位匹配失败根据规则移位 else: i = i + max(ault(b[1:], m), j - ault(string[i + j - 1], 0)) j = m #

匹配成功返回匹配位置 if j == 0: (i) i += 1 j = len(pattern)