问题标签 [knuth-morris-pratt]

我试图实现 knuth morris pratt 算法。文本中图案的最终外观没有被打印出来。count 变量保存模式在字符串中出现的次数的值。请帮助解决问题

我最近遇到了 KMP 算法，我花了很多时间试图理解它为什么起作用。虽然我现在确实了解基本功能，但我根本无法理解运行时计算。

我从 geeksForGeeks 网站获取了以下代码：https ://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/

该站点声称，如果文本大小为 O(n) 且模式大小为 O(m)，则 KMP 会在最大 O(n) 时间内计算匹配。它还指出可以在 O(m) 时间内计算 LPS 数组。

我真的很困惑为什么会这样。

对于 LPS 计算，请考虑： aaaaaacaaac 在这种情况下，当我们尝试计算第一个 c 的 LPS 时，我们将继续返回，直到遇到 LPS[0]，即 0 并停止。因此，本质上，我们将至少返回模式的长度直到该点。如果这种情况发生多次，时间复杂度将如何 O(m)？

我对 KMP 的运行时间有类似的困惑是 O(n)。

在发布之前，我已经阅读了堆栈溢出中的其他线程，以及有关该主题的各种其他站点。我仍然很困惑。如果有人可以帮助我了解这些算法的最佳和最坏情况以及如何使用一些示例计算它们的运行时间，我将不胜感激。再说一次，请不要建议我用谷歌搜索，我已经完成了，花了整整一周的时间试图获得任何见解，但失败了。

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

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

为什么 KMP O(n + m)？

我知道这个问题可能已经在这里被问了一百万次，但我还没有找到一个让我/我理解的解决方案或一个与我的例子相匹配的问题。

n = 文本
大小 m = 图案大小

我知道为什么它的 + m，这就是创建 lsp 数组进行查找所需的运行时。我不确定为什么我上面传递的代码是 O(n)。

我看到上面的“i”总是向前推进，除非它不匹配并且 j!= 0。在这种情况下，我们可以在 i 不向前移动的情况下进行 while 循环的迭代，所以它不完全是 O(n )

如果 lps 数组像 [1,2,3,4,5,6,0] 一样递增。如果我们在索引 6 处匹配失败，j 会更新为 5，然后是 4，然后是 3.... 等等，我们有效地经历了 m 次额外的迭代（假设所有不匹配）。这可能发生在每一步。

所以看起来像

并且将所有可能的 ij 组合也称为状态将需要一个m 数组，因此运行时不会是 O(n m)。

那么是我的代码读错了，还是for循环的运行时分析错了，还是我的例子是不可能的？

我想在流上实现搜索和替换算法，我将在其中创建一个将源流作为输入的流类，并且 who's read 方法将根据需要从源流中读取并作为流执行搜索/替换正在阅读。这将减轻整个数据集一次加载到内存中的情况，并在非常大的数据集上启用搜索和替换。

为此，我想我将从现有的搜索算法开始，将其调整为流方法，然后调整替换功能。

下面是我改编自在线示例的 Knuth Morris Pratt 实现。有没有人将这样的东西适应流方法？我需要考虑跨读取边界的搜索，我不确定我会怎么做。

然后我采用上述算法并将其改装为 Stream。作为概念证明，每次找到搜索模式时，流都会在其 read 方法期间引发一个事件。它目前具有无法跨读取边界进行搜索的限制。所以如果一次读取1024字节，源流的长度为2048字节，则执行两次读取，读取整个流。问题是，如果搜索模式从索引 1000 开始并且长度为 40 字节，则不会找到它。我认为一旦解决了这个问题，实际的替换功能就不会那么困难了。我正在寻找有关如何跨读取边界实现搜索的建议。它可能涉及缓存先前读取的部分。有人知道类似于此的流式实现或建议吗？

我正在做一个项目来比较 2 个字符串搜索算法的时间复杂度。由于某些问题，我丢失了以前的代码，因此不得不重写大部分代码。然而，这一次，我的 KMP 算法似乎运行得慢了很多，而且无论我输入什么，我都无法真正让它比我的 Boyer-Moore 运行得更快。这是我的代码：

例如，在我之前的结果中，对于单词“the”，Boyer-Moore 大约需要 260 毫秒，而 KMP 大约需要 184 毫秒。现在，Boyer-Moore 当然仍然需要大约 260 毫秒，但是 KMP 现在需要大约 330 毫秒。任何指向正确方向的指针将不胜感激。谢谢你。

我在我的程序中实现了 KMP 模式搜索算法来搜索对象表。我想知道如何评估我的功能的时间效率。

我读了一些资料，说 KMP 算法的时间复杂度是O(n) [不包括空间复杂度]

因此，我将遍历从 1 到 N 项的对象列表，在每个项中搜索模式匹配。一旦有比赛，我就会跳出循环，但这并不会真正影响我的评估（我认为）。

因此，由于我迭代了所有项目，所以我的大 O 表示法是：O(n^2)，因为它需要O(n)才能找到匹配项，而O(n)需要遍历我的所有项目。

这是我的一些见解的代码：

我在使用 Knuth-Morris-Pratt 找到模式 P = abacaaba 的正确故障链接时遇到问题。

这是我到目前为止所得到的：

k 1 2 3 4 5 6 7 8

P(k) 蕉麻

FLink(k) 0 0 1 0 1 1 1 1

1. 第一个始终为 0
2. 现在我们有 k(i) = a1 和 k(j) = b2，这些是不匹配的，所以它应该是 0
3. 现在我们有 k(i) = a1 和 k(j) = a3，它们是匹配的，a1 = 0，所以 a3 = 0 + 1 = 1
4. 现在我们将 i 和 j 向右跳一个，k(i) = b2 和 k(j) = c4，这些是不匹配的，所以我们将 i 跳回 1。现在 k(i) = a1，这是一个不匹配。我们不能再回去了，所以 c4 = 0
5. 现在 k(i) = a1 和 k(j) = a5，它们是匹配的。a1 的值为 0，所以 a5 = 0 + 1 = 1。
6. 我们再次将 i 和 j 放在右边。k(i) = b2 和 k(j) = a6。这是一个不匹配。我们将 i 放回 1，所以 k(i) = a1。a1 和 a6 匹配，a1 的值为 0，所以 a6 = 0 + 1 = 1。
7. 我们再次将 i 和 j 放在右边。k(i) = b2 和 k(j) = b7。这些是匹配的，b2 的值为 0，因此 b7 的值为 0 + 1 = 1。
8. 最后 k(i) = b2 和 k(j) = a8。这些不匹配，新的 k(i) 将是 a1。a1 和 a8 匹配，i 的值为 0，所以 a8 = 0 + 1 = 1。

我的老师给 FLink(k) 的答案是 0 1 1 2 1 2 2 3。我做错了什么吗？

所以我一直在研究子字符串搜索算法，发现大多数算法（如 kmp 和 rabin-karp 算法）在进行一些字符串匹配之前需要额外的时间复杂度来预处理时间。这样做有什么好处吗？为什么他们不直接跳到字符串匹配，以使大 O 时间复杂度不会下降到 O(m+n)？我尝试通过简单地跳过预处理时间来创建一个我认为是 O(n) 的子字符串算法（如果我错了，请纠正我）。我想知道为什么人们不这样做，请参阅下面的 C 代码。

编辑：

删除了 strlen 函数以避免任何不必要的时间复杂度

LPS（Longest Proper Prefix，也是后缀）算法如下：

部分看起来清晰，if (s.charAt(i) == s.charAt(j))但else部分不清楚。我们为什么这样做：

更具体地说，为什么j = arr[j - 1]有效？或者我们为什么要这样做？我们如何验证这一步的正确性？