请提供Boyer Moore 算法代码
时间: 2024-05-25 19:10:33 浏览: 11
以下是 Boyer Moore 算法的 Python 代码实现:
def boyer_moore_search(text, pattern):
# 计算 pattern 的长度
m = len(pattern)
# 如果 pattern 为空,则无需查找,直接返回 0
if m == 0:
return 0
# 建立坏字符规则表
bad_char = {}
for i in range(m):
bad_char[pattern[i]] = i
# 初始化 good suffix 数组和 suffix 部分是否是前缀数组
good_suffix = [0] * m
suffix_is_prefix = [False] * m
z = m - 1
for j in range(m-1, -1, -1):
# 查找最右边的与 pattern 的后缀匹配的位置
if is_suffix(pattern, j+1):
z = j + 1
good_suffix[j] = z - j
for j in range(m):
k = m - 1 - j
if border_with_suffix(pattern, k):
z = k
suffix_is_prefix[k] = z != m - 1 - j
# 开始匹配
i = 0
while i <= len(text) - m:
# 从后往前比较
j = m - 1
while j >= 0 and pattern[j] == text[i+j]:
j -= 1
if j == -1:
# 匹配成功,返回索引位置
return i
else:
# 计算坏字符规则和好后缀规则的滑动距离
bad_char_slide = max(1, j - bad_char.get(text[i+j], -1))
good_suffix_slide = 0
if j < m-1:
if suffix_is_prefix[j+1]:
good_suffix_slide = m - 1 - j - good_suffix[j+1]
else:
good_suffix_slide = m - 1 - border(pattern, j+1)
i += max(bad_char_slide, good_suffix_slide)
# 未找到匹配的 pattern
return -1
# 判断 pattern[p:] 是否是 pattern 的后缀
def is_suffix(pattern, p):
m = len(pattern)
return all(pattern[m-1-k] == pattern[p-1-k] for k in range(p-1, -1, -1))
# 计算 pattern[k:] 的最长前缀的长度,该前缀同时也是 pattern 的后缀
def border_with_suffix(pattern, k):
m = len(pattern)
i = j = k
while i >= 0 and pattern[i] == pattern[m-1-j]:
i -= 1
j += 1
return i == -1
# 计算 pattern[k:] 的最长前缀的长度
def border(pattern, k):
m = len(pattern)
i = j = k
while i >= 0 and pattern[i] == pattern[m-1-j]:
i -= 1
j += 1
return k - i
# 测试代码
text = 'ABAAABCD'
pattern = 'ABC'
print(boyer_moore_search(text, pattern)) # 输出:4
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cs](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)