字符串匹配算法：KMP与Boyer-Moore算法详解
字符串匹配是计算机科学中一个基础且重要的问题。在许多应用场景中，如文本编辑、搜索引擎、生物信息学等，都需要对字符串进行高效的匹配。本文将围绕字符串匹配这一主题，详细介绍两种经典的算法：KMP（Knuth-Morris-Pratt）算法和Boyer-Moore算法。
KMP算法
KMP算法是一种高效的字符串匹配算法，由Donald Knuth、James H. Morris和Vijay R. Pratt共同提出。KMP算法的核心思想是避免重复扫描已经匹配的字符，从而提高匹配效率。
KMP算法的基本原理
KMP算法通过构建一个部分匹配表（也称为“失败函数”或“next数组”），来记录模式串中每个位置之前的最大公共前后缀的长度。当发生不匹配时，可以利用这个信息跳过一些不必要的比较，从而提高匹配效率。
KMP算法的实现
以下是一个KMP算法的Python实现：
python
def kmp_search(text, pattern):
构建部分匹配表
def build_next(pattern):
next = [0] len(pattern)
k = 0
for i in range(1, len(pattern)):
while k > 0 and pattern[k] != pattern[i]:
k = next[k - 1]
if pattern[k] == pattern[i]:
k += 1
next[i] = k
return next
next = build_next(pattern)
i = j = 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
return i - j
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = next[j - 1]
else:
i += 1
return -1
示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern)) 输出：10
Boyer-Moore算法
Boyer-Moore算法是一种高效的字符串匹配算法，由Robert S. Boyer和J. Strother Moore共同提出。Boyer-Moore算法的核心思想是利用已知的模式串信息，从后往前进行匹配，从而减少不必要的比较。
Boyer-Moore算法的基本原理
Boyer-Moore算法包含两个阶段：坏字符规则和好后缀规则。
- 坏字符规则：当发生不匹配时，如果当前字符不是模式串的最后一个字符，则将模式串向右滑动，直到找到一个匹配的字符或者模式串的末尾。
- 好后缀规则：如果当前字符是模式串的最后一个字符，则检查模式串的末尾是否与文本的末尾匹配。如果匹配，则将模式串向右滑动；如果不匹配，则根据好后缀规则确定滑动距离。
Boyer-Moore算法的实现
以下是一个Boyer-Moore算法的Python实现：
python
def boyer_moore_search(text, pattern):
构建坏字符表
def build_bad_char_table(pattern):
bad_char = [-1] 256
for i in range(len(pattern) - 1):
bad_char[ord(pattern[i])] = i
return bad_char
构建好后缀表
def build_good_suffix_table(pattern):
n = len(pattern)
suffix = [0] n
l = [0] n
i = n - 1
j = n
while i > 0:
while j > 0 and pattern[i - 1] != pattern[j - 1]:
if suffix[j] == 0:
suffix[j] = i
j = suffix[j]
i -= 1
j -= 1
k = 0
i = 0
while i < n:
if suffix[i] == 0:
l[i] = k
i += 1
k += 1
else:
j = suffix[i]
k = max(0, k - 1)
while j > 0 and pattern[i - 1] != pattern[j - 1]:
if suffix[j] == 0:
suffix[j] = i
j = suffix[j]
i += 1
j += 1
return l
bad_char = build_bad_char_table(pattern)
good_suffix = build_good_suffix_table(pattern)
i = len(pattern) - 1
j = len(pattern) - 1
while i < len(text):
if text[i] == pattern[j]:
i -= 1
j -= 1
if j < 0:
return i - j
elif bad_char[ord(text[i])] > j:
i = i - j - bad_char[ord(text[i])]
j = len(pattern) - 1
else:
j = good_suffix[j]
return -1
示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(boyer_moore_search(text, pattern)) 输出：10
总结
本文详细介绍了两种经典的字符串匹配算法：KMP算法和Boyer-Moore算法。KMP算法通过构建部分匹配表来避免重复扫描，而Boyer-Moore算法则通过坏字符规则和好后缀规则来减少不必要的比较。这两种算法在处理字符串匹配问题时具有很高的效率，在实际应用中得到了广泛的应用。
Comments NOTHING