boyer-moore算法python

布满荆棘的人生 2024-02-21 11:00 43阅读 0赞

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更改为你自己的文本和模式来测试不同的输入。

发表评论取消回复

表情：

评论列表（有 0 条评论，43人围观）

还没有评论，来说两句吧...

相关阅读

相关 python排序算法

Python中有许多不同的排序算法，其中包括： 1. 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序 5. 归并排序 6. 堆排序除了这些常见的排序

川长思鸟来/ 2024年03月25日 08:33/ 0 赞/ 42 阅读

相关 dijkstra算法python

Dijkstra算法是一种用于寻找带权重图中从一个起始节点到其他节点的最短路径的算法。下面是一个使用Python实现Dijkstra算法的示例代码： import heapq

﹏ヽ暗。殇╰゛Y/ 2024年02月20日 08:46/ 0 赞/ 37 阅读

相关 Python优化算法—遗传算法

Python优化算法—遗传算法一、前言二、安装三、遗传算法 3.1 自定义函数 3.2 遗传算法进行整数规划

痛定思痛。/ 2023年09月27日 14:33/ 0 赞/ 145 阅读

相关 python 算法希尔算法

nums=[9,3,5,8,2,7,1] step=len(nums)//2 分组用//取整 while step>0: //退出循环条件

青旅半醒/ 2023年02月18日 14:05/ 0 赞/ 18 阅读

相关 python的算法分析,Python算法分析

Python算法分析算法分析可以在实施之前和实施之后的两个不同阶段分析算法的效率。他们是以下- 先验分析-这是算法的理论分析。通过假设所有其他因素(例如处理器速度)是

╰+攻爆jí腚メ/ 2023年01月17日 04:58/ 0 赞/ 131 阅读

相关 python算法入门

python算法入门排序排序算法很多，常见的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序的思想，在此介绍

雨点打透心脏的1/2处/ 2022年12月23日 03:57/ 0 赞/ 65 阅读

相关 python遗传算法_带有Python的AI –遗传算法

![python遗传算法][python] python遗传算法带有Python的AI –遗传算法 (AI with Python – Genetic Algorith

心已赠人/ 2022年12月10日 01:27/ 0 赞/ 240 阅读

相关【Python】KMP算法

文章目录字符串查找问题暴力求解算法 Python代码 KMP算法 next的递推关系

淩亂°似流年/ 2022年05月22日 03:59/ 0 赞/ 225 阅读

相关 Dijkstra 算法 python

def Dijkstra_is_algorithm(node): node = find_lowest_cost_node(costs) 在未处理的

太过爱你忘了你带给我的痛/ 2022年05月17日 04:34/ 0 赞/ 141 阅读

相关 python遗传算法

学习代码来源于：遗传算法python 一.主要思想遗传算法是根据达尔文的“适者生存，优胜劣汰”的思想来找到最优解的额，其特点是所找到的解是全局最优解，相对于蚁群算法可能出

左手的ㄟ右手/ 2022年02月20日 12:13/ 0 赞/ 319 阅读