问题标签 [boyer-moore]

我正在研究 Boyer-Moore 算法（从这里开始），我有一个快速的问题 - 第二遍需要什么（基本上只是通过找到该元素的频率来“确认”）。第一遍本身不能保证找到的元素是大多数元素吗？我考虑了几个例子，觉得一次通过就足够了。您能否提供一些例子来反驳我的感受？

代码（如果需要）如下：

编辑： 如果我理解正确，该算法仅适用于多数元素的频率确实大于(vector size())/2. 那么，真的需要第二遍吗？每当我们编写代码时，我们都会进行一些琐碎的完整性检查（例如检查输入向量是否为空），那么在这种情况下，为什么我们将“完整性检查”作为算法的一部分呢？或者还有更多的东西吗？

我想从a读取std::istream直到找到某个字符序列，即我想实现以下接口：

使用std::istreambuf_iterator，我相信这相当于std::search单遍迭代器的组合。不幸的是，std::boyer_moore_searcher需要随机访问迭代器。

是否有使用 C++ 标准库（以及与 的大小成比例的一点内存）对上述接口的任何简单实现sv，还是我必须自己编写代码？

所以我班上的一个练习是使用模式abc和字符串执行 Boyer-Moore 算法aabcbcbabcabcabc和abababababababab。我还打算记下比较的次数。

我使用扩展的坏字符规则完成了这项工作，但是今天有人告诉我，一旦在字符串中找到匹配项，就需要使用强好后缀规则。但是，由于模式长度仅为 3，我对如何在此处使用强好后缀规则感到有些困惑。

当完全匹配时，由于模式abc没有边框，当在字符串中遇到它时，我会简单地移动 3 个符号吗？

谢谢你！

我正在尝试使用 Boyer 和 Moore 方法找到多数元素。程序应该要求用户在第一行输入“n”行，然后将有“n”个数字跟随“n”行作为输入。（例如：用户在第一行输入 5，然后将有 5 个数字）接下来，使用 Boyer 和 Moore 方法找到输入数组的多数元素。如果输入数组中不存在多数元素，则执行 -1。无论我输入什么输入，我的程序输出都显示为 0。请您检查并更正我的程序好吗？

输出示例：4 12 12 1 12 12 /或：3 11 2 13 -1

我已经研究过 StackOverflow 上的各种解决方案，试图了解 Boyer-Moore 算法的功能，但是我正在寻找更多关于算法实际功能的分步说明（视觉学习对我来说要好得多）。

我试图理解这张图片，但我不完全理解为什么在比较 6 中它会向前跳过：

我希望看到它画得更好，但如果你能通过伪代码告诉我为什么会发生这种情况，我将不胜感激。

谢谢你。

根据工作伙伴的说法，以下实现 boyer moore 算法的效率不是很高。我似乎不知道我做错了什么，没有得到高质量的结果。

我已经对其进行了测试，并且效果很好，我唯一需要做的就是高效地工作。我可以得到任何帮助吗？

这是.java中的代码实现

我用 Fortran（我选择的语言）编写了以下代码，认为它会非常快。事实证明，它相当快，但比 FORTRAN 内在（索引）查找子字符串要慢得多。举个例子，如果我在一个完全随机的 5,000,000 个字符的字符串中搜索距离字符串末尾 1,000 个字符的字符串“月亮是气球”，我得到以下时间（平均超过 10 次运行在库存英特尔 HM370（Cannon Lake-H））。我正在运行 Windows 10，仅使用带有 -O3 和 -fno-checking 优化标志的 GCC Fortan）；我的代码（如下）~ 0.09 秒内在~ 0.03 秒我正在寻找有关重构代码以进一步加快速度的任何建议。

我需要在二进制数据（文件）中找到 unicode 文本。

我正在寻找可以在 macOS 上使用的任何 C 或 C++ 代码或库。因为我猜这对其他平台也很有用，所以我宁愿让这个问题不特定于 macOS。

在 macOS 上，NSString无法使用满足我对 unicode 精通需求的函数，因为它们不适用于二进制数据。

作为替代方案，我尝试了regexmacOS 上提供的 POSIX 兼容函数，但它们有一些限制：

• 它们不精通规范化，即如果我搜索预组合 (NFC) 字符，如果它在目标数据中以分解 (NFD) 形式出现，它将找不到字符。
• 不区分大小写的搜索不适用于拉丁 NFC 字符（搜索 Ü 找不到 ü）。

显示这些结果的示例代码如下。

有哪些代码或库可以满足这些需求？

我不需要正则表达式功能，但如果有一个正则表达式库可以处理这些要求，我也可以。

基本上，我需要使用以下选项进行 unicode 文本搜索：

• 不区分大小写
• 归一化不敏感
• 变音符号不敏感
• 适用于任意二进制数据，查找匹配的 UTF-8 文本片段

这是显示在 macOS 上使用 TRE 正则表达式实现的结果的测试代码：

输出是：

期望的输出：所有情况都应该给出“是”

我正在学习字符串搜索算法并了解它们的工作原理，但还没有找到足够好的答案来说明在哪些情况下 Rabin-Karp 算法会比 KMP 或 Boyer-Moore 更有效。我看到它更容易实现并且不需要相同的开销，但除此之外，我不知道。

那么，Rabin-Karp 什么时候比其他方法更好用呢？

我想尝试使用std::boyer_moore_searcher类。但是我遇到了两个问题：

1. 它在哪里？我正在使用 Visual Studio 2019，但它报告"namespace std has no member boyer_moore_searcher"。
2. Boyer Moore 算法的问题之一是对于 Unicode 字符，跳转表必须非常大。谁能告诉我boyer_moore_searcher班级是如何处理这个问题的？