问题标签 [knuth-morris-pratt]

我正在寻找一种用于合并字符串的算法（最好使用 java 实现）。

我的问题如下：

假设我有一个字符串数组/列表{"myString1" , "my String1" , "my-String-1" ... }值表示“ myString1 ”。

所以我想压缩我的清单。也许这可以用 KMP 来完成，或者也许有更合适的东西。

谢谢。

如何使用 KMP 算法查找不包含字符串 B 作为子字符串的字符串 A 的不同子字符串的数量？

我使用 KMP 算法解决了另一个问题，但找不到如何用 KMP 解决这个问题。

提前致谢。

搜索包含不完全匹配的单词的短语的最佳方法是什么，例如：

我想搜索：

是否有使用 mongodb 的提示，或者我是否使用来自 python 的 Knuth-Morris-Pratt 字符串匹配（这会杀死服务器）？

KMP 算法在最佳情况下的最小比较次数是多少？

在研究字符串的 Knuth-Morris-Pratt 算法时：

对于模式：

我被困在一个步骤上。我将突出显示我目前卡住的步骤。

我不明白上面的步骤。我希望上述步骤是：

请解释“正确”步骤的逻辑/原因。

如我所见，在 KMP 中构建故障/前缀表的主要功能（在所有在线资源中，即使在此答案中_ 如下：

我无法理解这部分：
j = failure[j - 1];

为什么我们不这样做，j--而不是返回字符串？我们如何知道j使用失败的表进行更新是正确的？

我一直在阅读有关 Knuth-Morris-Pratt 算法的 Wikipedia 文章，我对如何在跳转/部分匹配表中找到这些值感到困惑。

如果有人可以更清楚地解释捷径规则，因为这句话

“假设我们发现了一个适当的后缀，它是一个适当的前缀，以 W[2] 结尾，长度为 2（可能的最大值）”

令人困惑。如果正确的后缀以 W[2] 结尾，它的大小不是 3 吗？

另外我想知道为什么 T[4] 不是 1 当有大小为 1 的前缀和后缀时：A.

感谢您提供的任何帮助。

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

KMP

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

BM

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

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

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

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

我的教授解决了kmp故障功能如下：

从网上查到的其他文字，我发现可能是错的，我又回去跟他确认，他告诉我他完全正确。有人可以通过简单的逐步方式向我解释为什么他认为这是对还是错？谢谢

我正在尝试在 Perl中实现Knuth Morris Pratt 算法。以下是我的代码，我参考了 Perl First Edition 中的 Mastering Algorithms 算法。当我运行代码时，它会打印 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 作为结果。我哪里错了？

代码：