问题标签 [boyer-moore]

我有一个关于我学校的测验问题

“Boyer Moore 算法的最坏情况时间复杂度为 O(MN)，其中 M 是字符串的长度，N 是模式的长度。”

这是真假问题，我对上面的陈述回答了假，因为我总是读到 N 是文本的长度，M 是模式的长度，但我的导师说你如何定义 M 和 N 并不重要，因为它索赔声明是真的是正确的吗？如果不是，我怎么能证明他的说法在科学上是错误的？

我的一本教科书中有一个问题如下。

你会得到总统选举的结果。每张选票都是一张一张的，每张选票上都写着候选人的名字（假设候选人的名字用数字表示）。在公布结果之前，候选人的总数和投票的人数是未知的。所有有效的选票都以一张作为输入，这个过程总共重复2次。我们只有 2 个简单的变量可以用于整个过程。您必须设计一种算法，该算法可以确定是否有候选人获得了投票者的多数票（即超过 50%）。如果存在这样的候选人，请打印候选人姓名，否则打印“blah blah blah”

现在我首先想到的是使用Boyer-Moore 多数算法并不断更新多数和计数器下一个结果出现时立即变量。如果我没有说清楚，结果不会存储在数组或其他任何地方。你得到一张选票的通知，然后你计算（这一直持续到所有选票都用完，这意味着我无法访问任何以前的信息）。无论此信息是否存储在数组中，我知道我仍然可以运行该算法的第一次迭代以获得“可能的”多数结果，因为该算法总是产生一个。我的问题在于第二次迭代。我一次又一次地看到结果。我应该如何验证我的原始结果是否确实是多数？有没有其他方法可以让我只用 2 个变量来解决它？

我试图找到str.replace()内置 python 的时间复杂度，这是我设法收集的数据（这里和其他网站）：

我知道replace()是基于 Boyer–Moore 算法，它需要 O(n*m) 的最坏情况时间来找到一个子字符串，但这是针对单个子字符串吗？

replace()当它找到第一个子字符串然后再次开始搜索时是否返回“固定”字符串的副本？

当我们多次出现子字符串时，例如以下示例：

如果它一次只能替换一个子串，那么对于单个子串，我们得到 O(n*m)，乘以子串的数量，最大值为 n/m。这是O（n ^ 2）！

假设一个简单的循环需要 O(n)，比如：

那有意义吗？我错过了什么吗？

内置的 replace() 是否会因多次替换而存在缺陷，或者它是否以一种从中断处继续的方式实现？

我需要一个给我的学生，但找不到任何他们能理解的简化版，而且我没有足够的时间自己制作。任何帮助都可以救我。谢谢！

我正在做一个项目，但没有找到任何有用的资源来说明如何将带有多个单词的子字符串与字符串匹配。

例如： substring = "I can be found in this string" 在 string = "Now, I can be found in this string example"

我不能使用该.find()方法或正则表达式并使事情变得更复杂，边缘情况包括：

"reflexion mirror"不匹配"'reflexion mirror'"但匹配"(reflexion mirror)"

"maley"不匹配"o'maley"

"luminate"火柴"'''luminate"

"luminate"火柴"luminate__"

"george" 不匹配"georges"

每当字符在字符串中加上"__hello world__"or"''hello world''"时，它都不会干扰匹配"hello"or"world"

我正在使用 Boyer Moore 来查找除了这些看似冲突的边缘情况之外的有效子字符串。哦，是的，我也忘了提到这个解决方案应该强调时间复杂度的性能。

我word.translate({ord(c): None for c in string.whitespace}).lower()用来预处理我的字符串和子字符串，结果是这样的：

"asuggestionboxentryfrombobcarterdearanonymous,i'mnotquitesureiunderstandtheconceptofthis'anonymous'suggestionbox.ifnoonereadswhatwewrite,thenhowwillanythingeverchangebutinthespiritofgoodwill,i'vedecidedtooffermytwocents,andhopefullykevinwon'tstealit(ha,ha).iwouldreallyliketoseemorevarietiesofcoffeeinthecoffeemachineinthebreakroom.'milkandsugar','blackwithsugar','extrasugar'and'creamandsugar'don'toffermuchdiversity.also,theselectionofdrinksseemsheavilyweightedinfavorof'sugar'.whatifwedon'twantanysugar?"

关于如何解释这些边缘情况的任何想法？

谢谢

编辑

有一个警告'要被视为一个角色

这是我从中收集边缘案例的单元测试：

我的正常程序如下：

问题是第二步需要很多时间，因为文件很大。总文件内容被加载到 wstring 上，这通常不是必需的，因为 boost::algorithm::boyer_moore 无论如何都会跳过读取大部分内容。

因此，跳过该步骤将大大提高速度，因此我需要一个在 std::wifstream 上的随机访问迭代器，例如 std::wifstream::const_iterator。

如何简洁地实现一个？

我正在尝试创建一个基于 ocr Web 的 pdf 查看器，用户可以在其中搜索手写文本。对于搜索功能，我将 pdf 图像发送到 django 服务器，它使用 tesseract 识别图像中的文本并返回一个字典，其中键作为单词，值作为坐标。我很困惑如何使用该字典来显示结果（该字典给出单词及其整个页面的坐标）。我尝试了 Boyer Moore 算法，但为此我需要在用户端将整个字典转换为字符串。

我最近一直在了解不同的字符串搜索算法，例如Knuth-Morris-Pratt和Boyer Moore 算法，并且在这样做的过程中，我了解了一些关于它们的一些细节，我无法消化这些细节，或者对这些算法有了自己的理解，但是仍然不确定它们的正确性。

问题：

1. 这个问题的最佳答案表明，如果字母表很小，KMP 效果很好。为什么会出现这种情况，为什么 Boyer 的算法在这种情况下不能比 KMP 表现得更好？
2. KMP 和 Boyer 算法性能最差的每个例子是什么？我已经发现，对于像这样的例子 Boyer 会给出最差的性能。那正确吗？

文本=' AAAA....13 A'S '

模式='AAA'

3.我能够理解 KMP 的正确前缀方面，并且能够消化这样一个事实，即它在跳过文本的已经匹配部分时不会跳过可能的匹配项，但即使我确实得到了Bad Character Heuristic背后的直觉 和Good Suffix Heuristic of Boyer 算法，它专注于跳过字符，以便模式与未来可能的匹配一致，我仍然无法让自己理解这两种启发式如何保证跳过的字符无论如何都不会匹配。

给定文档第 2 页的第 4 段也谈到了相同的内容，即我们可以跳过文本的某些字符而不看它们。为什么我们可以忽略它们？

4. 用 Layman 的语言，我们可以声称 KMP 和 Boyer 算法之间的区别在于 KMP 通过跳过已经匹配的字符来工作，而 Boyer 通过跳过不会产生任何区别的字符来工作，因为文本上窗口的当前位置已经有一个未匹配项.

它们都被视为字符串匹配算法吗？

假设我想检测两个字符串有多接近，所以我想匹配它们。因此我会使用 Levenshtein Word Distance。但是，如果字符串是整个句子，也许首先我应该使用搜索算法，还是有点矫枉过正？这两种算法是否相互补充？在我看来，它们之间的使用有一些重叠，但我无法解释它可能是什么。因此，我想问两者之间的关系是什么？

是的，这几乎是一个菜鸟问题。

我试图在 python 中找到 str.replace() 内置函数的时间复杂度（Big O）

我知道最坏的情况是 O(n m)* 来找到一个子字符串，但是如果我们在一行中使用三次替换怎么办

我正在尝试在某个字符串中交换 char1 和 char2，备用代码使用的是 O(n) 时间复杂度的 for 循环。但是对于上面的代码，大O会变成3倍，还是变成n^3？那有意义吗？