本文主要是介绍boyer-moore算法python,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Boyer-Moore算法是一种用于字符串搜索的高效算法,它通过跳过尽可能多的字符来减少比较的次数。下面是一个简单的Python实现Boyer-Moore算法的示例:
def build_bad_char_table(pattern):
bad_char_table = {}
pattern_length = len(pattern)
for i in range(pattern_length - 1):
bad_char_table[pattern[i]] = pattern_length - i - 1
return bad_char_table
def build_good_suffix_table(pattern):
pattern_length = len(pattern)
good_suffix_table = [-1] * pattern_length
last_prefix_position = pattern_length
for i in range(pattern_length - 1, -1, -1):
if is_prefix(pattern, i + 1):
last_prefix_position = i + 1
good_suffix_table[i] = last_prefix_position + pattern_length - i - 1
for i in range(pattern_length - 1):
j = pattern_length - 1 - i
if is_suffix(pattern, j):
last_prefix_position = j
good_suffix_table[j] = min(good_suffix_table[j], pattern_length - 1 - last_prefix_position + j)
return good_suffix_table
def is_prefix(pattern, p):
pattern_length = len(pattern)
j = 0
for i in range(p, pattern_length):
if pattern[i] != pattern[j]:
return False
j += 1
return True
def is_suffix(pattern, p):
pattern_length = len(pattern)
i = 0
j = p
while j < pattern_length:
if pattern[i] != pattern[j]:
return False
i += 1
j += 1
return True
def boyer_moore_search(text, pattern):
bad_char_table = build_bad_char_table(pattern)
good_suffix_table = build_good_suffix_table(pattern)
pattern_length = len(pattern)
text_length = len(text)
i = 0
while i <= text_length - pattern_length:
j = pattern_length - 1
while j >= 0 and pattern[j] == text[i + j]:
j -= 1
if j < 0:
# Pattern found at index i
print("Pattern found at index", i)
i += good_suffix_table[0]
else:
# Shift based on the bad character rule and good suffix rule
bad_char_shift = bad_char_table.get(text[i + j, -1])
good_suffix_shift = good_suffix_table[j]
i += max(bad_char_shift, good_suffix_shift)
# 测试Boyer-Moore搜索
text = "This is a sample text for testing the Boyer-Moore algorithm."
pattern = "Boyer-Moore"
boyer_moore_search(text, pattern)
这个示例包含了Boyer-Moore算法的实现,包括构建坏字符表(bad character table)和好后缀表(good suffix table)。然后,boyer_moore_search函数使用这些表来执行搜索。在这个示例中,它会输出找到的模式的索引位置。你可以将text和pattern更改为你自己的文本和模式来测试不同的输入。
这篇关于boyer-moore算法python的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!