问题标签 [knuth-morris-pratt]

我试图在ideone中解决大海捞针问题，但我得到了一个 SIGSEGV。

这是我的代码：

有人可以解释为什么我只在上传输入时才收到此错误，而该程序通常运行良好且花花公子。

I have a trouble with understanding this implementation of the Knuth-Morris-Pratt algorithm in Haskell.

http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell

In particular I don't understand the construction of the automaton. I know that it uses the "Tying the Knot" method to construct it, but it isn't clear to me and I also don't know why it should have the right complexity.

Another thing I would like to know is whether you think that this implementation could be easily generalized to implement the Aho-Corasick algorithm.

Thanks for your answers!

我已经实现了用于在字符串 B 中搜索字符串 A 的 Knuth-Morris-Pratt 算法。如果找到该字符串，则返回字符串的第一个位置，否则返回 -1。但是现在我想计算字符串 B 中字符串 A 的总出现次数。

我尝试了一种简单的方法并且它正在工作，但这似乎并不有效，因为使用大字符串需要很多时间。

谁能帮我解决这个问题？我想要一种更有效的方式来使用 KMP。

这是我的测试。

//编辑：我解决了我的问题，我只需要正确阅读维基百科文章。

这是我在 ItoA 中看到的伪代码：

我的疑问是为什么在第 6 行我们这样做k = pi[k]而不是k--在我看来这应该是检查长度前缀的方式k（因为如果P[k+1] != P[q]这意味着k+1无法实现也是后缀的长度前缀）也可以是后缀，那与 相比P[q]，我也认为如果我们这样做，运行时间将保持不变。

鉴于以下问题：

定义 ：

让 S 是字母 Σ 上的字符串。S'是最小的周期S ifS'是最小的字符串，使得 ：

S = (S')^k (S''),

S''的前缀在哪里S。如果没有这样的S'存在，那么S就不是周期性的。

示例：S = abcabcabcabca。Thenabcabc是一个周期 since S = abcabc abcabc a，但最小的周期是abcsince S = abc abc abc abc a。

给出一个算法来找到输入字符串的最小周期S或声明它S不是周期性的。

提示：你可以这样做O(n)...

我的解决方案：我们使用 KMP ，它在 O(n) 中运行。

根据问题的定义，S = (S')^k (S'')，那么我认为如果我们创建一个最短周期的自动机，并找到一种方法来找到最短周期，那么我就完成了.

问题是在哪里放置自动机的FAIL箭头......

任何想法将不胜感激，

问候

维基百科声称可以在 O(n) 时间内计算出故障函数表。

让我们看看它的“规范”实现（在 C++ 中）：

为什么它在 O(n) 时间内工作，即使有一个内部 while 循环？我对算法的分析不是很擅长，所以有人可以解释一下吗？

我正在尝试解决HackerRank 挑战，但遇到了问题。显然，如果出于性能要求（我尝试过），O（n ^ 2）的蛮力解决方案将无法解决，因此我开始寻找更优雅的解决方案。那是我登陆KMP的时候。在本教程之后，我实现了它。

但是，挑战表明您实际上可以在字符串中存在一个不匹配，因此我尝试在我的代码中添加该功能。但是，我得到的结果不正确，我完全不知道为什么。有人可以看看我的解决方案并指出正确的方向吗？

我正在阅读维基百科上的KMP 算法。“建表算法的伪代码描述”部分中有一行代码让我感到困惑：let cnd ← T[cnd]

它有一条评论：(second case: it doesn't, but we can fall back)，我知道我们可以后退，但为什么是 T[cnd]，有原因吗？因为它真的让我很困惑。

这是建表算法的完整伪代码：

我阅读了的源代码，java.lang.String我惊讶地发现String.indexof()不使用Knuth-Morris-Pratt 算法？众所周知，KMP 更有效。那么为什么不使用它String.indexOf()呢？

我周围有人告诉我，对于短字符串，KMP 已经足够了，但是如果您需要性能并且打算使用大字符串，那么它不是一个好的选择。不过他没有告诉我细节。

所以，这是我的问题：

1. 为什么我们不使用 KMPString.indexOf()呢？
2. 为什么 KMP 不是大字符串的好选择？

我被要求了解 KMP DFA，而我在书中发现的就是这种实现，但我们的讲师一直称之为“前缀函数”。我真的不明白这个功能是哪一部分，有人可以给我解释一下吗？很抱歉，如果有人问过这个问题，但我找不到。