问题标签 [boyer-moore]

我正在研究这个算法，但模式和文本不匹配。

文字为：AADBCCAAA 图案为：CCAAA

我已经创建了坏符号表和好后缀表。

坏符号：

！AC（! 表示不在模式中的字母）
5 1 3

好后缀：
k d2
1 2
2 6
3 6
4 6
5 6

至于我的搜索：
AADBCCAAA
CCAAA 既然没有匹配，shift 3 因为C导致不匹配

这会将模式中最右边的 A 与文本中倒数第二个 A 对齐。这表示

d1 = 3-2 = 1 和 d2 = 6。两者的最大值为 6，因此移位 6。

对于 Boyer-Moore，这是否意味着由于您不能移动 6，它只会将模式与文本末尾进行比较并找到匹配项，还是我做错了什么？

我理解坏符号表。在好的后缀表中，距离不应该计算为从最右边的模式出现到模式文本末尾的距离吗？在这种情况下，下表不应该将所有距离 (d2) 都设为 1（最后一个条目为 5 除外），因为在它的最左侧可以使用相同的模式？

在类似的条件下，也从未理解下表。有什么帮助吗？

参考：

问题 - 第 6 页，问题 7。

答案 - 第 11 页

计算机算法的设计与分析- Anany Levitin ( https://umutzafer.files.wordpress.com/2012/01/solu7.pdf )

文本 -计算机算法的设计和分析 - Anany Levitin（第 263 页）

我已经使用 node.js 编写了 Boyer-Moore horspool 字符串匹配算法。该程序工作，但总是输出 -1，如果模式字符串不在指定文本中，它应该输出。

我终其一生都无法弄清楚什么是行不通的，我会非常感谢提示我需要解决的问题。

我的代码

任何帮助将不胜感激。谢谢你！

I've been working on implementing the Boyer-Moore algorithm in Java and I've hit a problem. The document (http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf) shows two examples for delta2(j) tables. The program I have made correctly calculates all the delta values, except delta(2) (the first B). My program claims that delta(2) is 2 (and that rpr(2) is 8). I have done the work on paper and it appears that this calculation is correct, but it disagrees with the document.

I am fairly certain that the document doesn't have a mistake so does anyone know if I have done something wrong.

根据我的理解，要找到多数元素 Boyer-Moore 多数投票算法是 O(1)，即它是恒定的，并且与输入的大小不成比例。那么为什么 thi wiki 链接提到对数空间 {\displaystyle O(\log n)} O(\log n)

这是供参考的程序

考虑以下带有元素的数组：

该算法不返回 5 作为多数元素，但在第一遍结束时将 2 视为计数为 0 的多数元素。

这是伪代码：

在此迭代结束时，num1 将包含元素“2”并且计数将为 0。我应该如何使算法工作以返回元素“5”？

我有两个文件（一个是bash脚本文件，另一个是cpp文件） bash文件（horsepool.bash）如下

cpp文件如下（horsepool_traditional.cpp）

执行 bash 文件（horsepool.bash）后，出现以下错误： 错误图像

我该如何解决这些错误？提前致谢。

我想把我的 Boyer - Moore 算法变成星期天（快速搜索）。目前我有一个工作版本的 Boyer - Moore 字符串搜索算法：

我一直在查看以下 2 个解释星期日（快速搜索）算法的链接，但我不确定如何将 BM 更改为星期日：

http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm

http://www-igm.univ-mlv.fr/~lecroq/string/node19.html

我会很感激任何提示。

此代码中存在致命错误：

第 108 行删除了调用时传递引用。这是 Boyer Moore 算法

函数坏字符

功能好后缀

函数boyer_moore

是什么导致了这个错误？

我会说是的，因为使用了正确的表格来确定您必须跳过多少字符。对此有什么想法吗？