问题标签 [boyer-moore]

在将Boyer–Moore 字符串搜索算法应用于字符串时：

有一个模式：

算法流程如下：

但是当将相同的算法应用于相同的字符串时：

但模式略有不同：（将第一个 E 替换为 T）

算法流程如下：

从第一个例子： 在第二步，E是在E

而在第二个例子中： 在第二步中，T不是在空格下E而是在空格下

这是为什么 ？T字母表和分别E在单词TXAMPLE和中有什么区别EXAMPLE？

我一直试图理解Boyer–Moore 字符串搜索算法中的移位规则，但还没有理解它们。我在维基百科上读到这里，但这太复杂了！

如果有人以简单的方式列出规则，那将有很大帮助。

I've written a Java function that implements the Boyer-Moore algorithm to search for a given substring in a char array. It returns a list of every index where the substring is found in the array. For example, if the char array being searched contained the phrase "The Walking Dead" and the substring given as a parameter was "king", a list of size one containing the value 7 would be returned.

I would like to change this function so that only indexes of substrings that are full words in the char array would be returned. So the previous example would return an empty list, but if the substring was changed to "The", "Walking" or "Dead", lists of size 1 would be returned with values 0, 4, and 12 respectively.

Is this sort of functionality possible to implement using the Boyer-Moore algorithm? Are there any other string searching algorithms that would be able to produce these results efficiently?

我编写了一个程序来搜索段落中的给定短语，并在该段落中用花括号将短语括起来。我已经使用 BoyerMoore 的算法进行搜索。同时我还需要提高程序的性能。虽然我得到了所需的输出，但性能是灾难性的。

这是代码：

我可以实施或做些什么来提高我的程序的性能？我应该切换到另一种字符串搜索算法吗？

如果有人可以帮我解决这个问题？

我根据这个站点使用了 Boyer Moore 算法。这仅在文本中实现一次模式搜索，然后程序退出。任何人都可以帮助我修改此代码，以便通过其开始和结束索引多次找到该模式吗？

我想实现处理通配符的 Boyer Moore Horspool 算法的概括（匹配单词中的任何字母）。这意味着该模式h _ _ s e将在此文本中出现两次：horsehouse.

我需要帮助来实现这一点，我无法对算法有足够深入的了解来自己解决这个问题，一些提示？

我在 C++ 中实现 BMH 算法时遇到了一些麻烦。

这是代码：

它适用于大多数示例，但有一些示例不起作用（到目前为止，我发现只有从不同来源下载的大量测试）。

我想知道我在哪里/做错了什么（我真的不想要代码）。

编辑：由于评论

您知道如何在不实现完整的 Boyer-Moore 版本的情况下使该算法运行得更快吗？

http://igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140

我不知道那个函数：“OUTPUT(j)”是什么意思，有人可以帮我吗？函数 MAX()？非常感谢。

我目前正在学习模式匹配算法，并且遇到过这两种算法。我有以下一般想法：

KMP

• 从左到右比较文本
• 使用故障阵列智能转移
• 需要 O(m)，其中 m 是模式的长度，来计算失败数组
• 需要 O(m)，空间
• 花费 O(n)，时间来搜索一个字符串

BM

• 比较最后一个字符的模式
• 使用坏字符跳转和好的后缀跳转
• 需要 O(m + 字母大小) 来计算表格
• 需要 O(m + 字母大小), 空间
• 需要 O(n)，但通常更好地搜索

我遇到了以下引发此问题的问题（对或错）：

如果我们想在许多不同的文本中重复搜索相同的模式，Knuth-Morris-Pratt (KMP) 算法是一个不错的选择。

所以我相信答案是正确的，因为假设每次你在不同的文本上运行算法时，预处理只是 O(n)，而对于 BM，它是 O(n + 字母大小)。但是，我不确定我是否做出了正确的假设，即每次重新运行算法时都会重新计算一个新表。因为说文本总是落在英文字母表中。我只需要计算一次表并重用该表。因此，归根结底，这个问题的答案是否取决于算法都在同一字母表中包含的文本上运行的事实，还是有其他可能影响它的因素？

这是我对 BMH 算法的实现（它就像一个魅力）：

我试图修改它以返回所有匹配项，而不仅仅是第一个索引，但我在任何地方都得到 IndexOutOfRangeException D：

显然我遗漏了一些重要的东西，或者我没有正确理解它是如何工作的。我究竟做错了什么？