boyer moore算法c语言,Boyer-Moore 算法

绝地灬酷狼 2022-10-15 11:51 107阅读 0赞

![3802066df593?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][3802066df593_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

image.png

“坏字符规则”。这个规则说，当我们做字符比较，并且发生错配时，一旦发生错配，我们就跳过下面的比对，直到发生以下这两件事之一：要么“错配”变成了一个“匹配”，或者模式“P”完全跳过了这个错配的字符。

step1 没匹配上，P向前条两格，直到上下C 匹配，step2 没匹配上，如果A 不再P里面，直接跳过所有的P

![3802066df593?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][3802066df593_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

image.png

Boyer-Moore算法的后一个组成部分，是另一个规则，它被称为“好后缀规则”。这个规则说，让“t”等于内部循环中，匹配的子字符串，所以，我们用小写的“t”来代表这个匹配上的子字符串。

step1 有错配， 把“TAC” 看成一个整体，P里面下一个TAC和这个比较，有的话就是step2，没有的话直接跳过

一般都是两个原则一起来的

![3802066df593?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_source=recommendation][3802066df593_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]

image.png

哪个跳过的多，用哪个。

step1: bc ==6, gs==0, 用bc

step2: bc==0, gs==2, 用gs

step3: bc==2,gs==7, 用gs

代码实现

def string\_match\_boyer\_moore(string,match,start=0):

string\_len = len(string)

match\_len = len(match)

end = match\_len - 1

if string\_len < match\_len or match\_len==0:

print ('Not Found')

return start;

while string\[end\] == match\[end\]:

end -= 1

if end == 0:

print ('Success Position:' + str(start))

return

idx = contain\_char(match,string\[end\])

shift = match\_len

if idx > -1:

shift = end - idx

start += shift

string\_match\_boyer\_moore(string\[shift:\],match,start)

def contain\_char(s,c):

for i in range(len(s)):

if c == s\[i\]:

return i

return -1

string\_match\_boyer\_moore('here is a simple example','example')

def find\_boyer\_moore(T,P):

n,m=len(T),len(P)

if m==0:return 0

last = \{\}

for k in range(m):

last\[P\[k\]\]=k

i=m-1

k=m-1

while i

if T\[i\]==P\[k\]:

if k==0:

return i

else:

i -= 1

k -= 1

else:

j = last.get(T\[i\],-1)

i+=m-min(k,j+1)

k=m-1

return -1

T='here is a simple example'

p='example'

i=find\_boyer\_moore(T,p)

print(i)

[3802066df593_utm_campaign_maleskine_utm_content_note_utm_medium_seo_notes_utm_source_recommendation]: /images/20221014/1ff8f7d2703143ff93775d8b817557d6.png

发表评论取消回复

表情：

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

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

相关阅读

相关 boyer-moore算法python

Boyer-Moore算法是一种用于字符串搜索的高效算法，它通过跳过尽可能多的字符来减少比较的次数。下面是一个简单的Python实现Boyer-Moore算法的示例： def

布满荆棘的人生/ 2024年02月21日 11:00/ 0 赞/ 43 阅读

相关【算法】Boyer-Moore 算法

目录 1.概述 1.1.Boyer-Moore 算法介绍 1.2.坏字符规则表 1.3.好后缀规则表 1.4.

约定不等于承诺〃/ 2024年02月17日 13:01/ 0 赞/ 40 阅读

相关深入理解Boyer-Moore算法：Java实现与示例

深入理解Boyer-Moore算法：Java实现与示例 Boyer-Moore算法是一种高效的字符串搜索算法，用于在文本中查找指定的模式字符串。相比于传统的搜索方法，Bo

柔光的暖阳◎/ 2023年10月15日 06:59/ 0 赞/ 119 阅读

相关 LeetCode_Boyer-Moore 投票算法_中等_229.求众数 II

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

亦凉/ 2023年10月06日 18:50/ 0 赞/ 46 阅读

相关 LeetCode_Boyer-Moore 投票算法_简单_169.多数元素

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于

水深无声/ 2023年10月06日 18:47/ 0 赞/ 49 阅读

相关面试题 17.10. 主要元素【Boyer-Moore 投票算法】

[Boyer-Moore 投票算法][Boyer-Moore] define debug(x) cout<<x<<": "<<(x)<<endl;

不念不忘少年蓝@/ 2022年10月19日 05:33/ 0 赞/ 146 阅读

相关 boyer moore算法c语言,Boyer-Moore 算法

![3802066df593?utm\_campaign=maleskine&utm\_content=note&utm\_medium=seo\_notes&utm\_sou

绝地灬酷狼/ 2022年10月15日 11:51/ 0 赞/ 108 阅读

相关字符串匹配的Boyer-Moore算法

![Center][] ![Center 1][] ![Center 2][] ![Center 3][] ![Center 4][]

ゞ浴缸里的玫瑰/ 2022年08月19日 11:28/ 0 赞/ 86 阅读

相关字符串匹配算法——Boyer-Moore算法

字符串匹配算法很多，Boyer-Moore算法也不算是效率最高的算法，它常用于各种文本编辑器的”查找”功能（Ctrl+F）。比较经典的字符串模式匹配算法还有：Horspo

Bertha 。/ 2022年08月02日 12:37/ 0 赞/ 170 阅读

相关 Boyer-Moore字符串搜索算法

该算法的主要观点是：如果将模式的结尾与文本进行比较，则可以进行文本跳转而不是检查文本的每个字符。这样做的原因是将文本排列在图案中，将图案的最后一个字符与文本中的字符进行比较。如

蔚落/ 2022年06月18日 00:55/ 0 赞/ 216 阅读