问题标签 [knuth-morris-pratt]

告诉我们 KMP 故障表的正确函数是什么？

我看过一对夫妇，但他们很困惑。我对后缀和前缀以及如何匹配它们感到有些困惑？

我相信我们从开始，-1但0我似乎无法理解表格的其余部分。

我对KMP（Knuth-Morris-Pratt）和Regex（基于 DFA）搜索之间的关系感到困惑。

我的想法是 KMP 不能使用正则表达式符号（例如，(A|B){2}C），因此它只能搜索“单个”字符串（例如，AC或BC，但不是AC|BC）。这是真的？

另一个问题，如果模式是单个字符串 ( ABABAC)，它们本质上是否使用相同？

我想使用 KMP 算法解决UVA 10298 -“Power Strings”问题。在这篇博客中，展示了如何使用失效函数来计算最小长度重复子串的技术。该技术如下：

1. pi[ ]计算给定字符串的前缀-后缀表。
2. 令len为字符串长度，并last_in_pi为存储在pi表的最后一个索引处的值。
3. 检查len % (len - last_in_pi) == 0是真是假。如果为真，则最小长度重复子串的长度为(len - last_in_pi)，否则为给定字符串的长度。

我了解什么是失败函数以及它如何用于在文本中查找模式，但我很难理解这种技术的正确性证明。

自从 4 天以来，我一直在阅读有关字符串和一些用于模式匹配的算法，为此我得到了 KMP 搜索算法，这很好，但我也知道还有另一种字符串匹配方法，它在空间和时间复杂度上与 KMP 相同，但有一个简单的解决方案。

该算法是Z-算法。

所以为此我搜索了谷歌，但我没有找到一个很好的算法解释。您能解释一下如何创建模式数组以及如何应用搜索程序吗？如果您将提供 C++ 代码，那就太好了。

我正在尝试实现 Knuth Morris Pratt 算法以在 java 中进行模式搜索，但它没有给出任何结果 prefixTable 生成器代码运行良好，因为我已经检查过了，但是用于搜索的主要代码不起作用

这是前缀生成器算法

作为输出，它没有给出空白，表明它在某些边界情况下没有找到模式

I've used the pseudocode from Wikipedia in an attempt to write a KMP algorithm in Haskell.

It's giving "index out of bounds" when I try to search beyond the length of the pattern and I can't seem to find the issue; my "fixes" have only ruined the result.

在最终了解了 KMP 算法之后，它的复杂性仍然不清楚。对于模式 M 的长度和文本 N 的长度，我知道，在最坏的情况下，它是 O(N+M) （仍然无法解释，为什么），但为什么平均是 O(N)案子？提前感谢您的帮助。

我正在尝试在 Java 中实现上述算法。但是我遇到了一个越​​界异常，我不知道如何解决这个问题。

我只是逐行翻译伪代码。

这是代码：

编辑：我已经用下面的 piyush 实现更新了代码，纠正了我的一些问题。然而还有另一个问题。

我使用这些测试了 KMPMatcher：

1) System.out.println(KMPMatcher("bacabab","bab")); // returned[2,4]

2) System.out.println(KMPMatcher("bdacabdacb","bab")); // returned[3]

数字 1 应该只返回 4，数字 2 应该只返回一个空列表。为什么会这样？我正在尝试使用这些输入绘制跟踪并将其与伪代码进行比较。我认为这与中的索引有关if(q==m-1)（因为与伪代码版本相比，它没有比较正确的东西？）而且我不知道如何解决它。请问有什么帮助吗？

我试图比较数据库和输入表单中的单词。我想数相同的单词，但结果不正确。

输入：方法或算法

tb_keyword

结果

1

预期结果

2

代码：

我正在关注 Cormen Leiserson Rivest Stein (clrs) 的书，并遇到了用于字符串匹配的“kmp 算法”。我使用 Python（按原样）实现了它。

但是，由于某种原因，它似乎不起作用。我的错在哪里？

代码如下：