问题标签 [knuth-morris-pratt]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
haskell - Knuth-Morris-Pratt algorithm in Haskell
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!
algorithm - KMP 计数字符串出现次数
我已经实现了用于在字符串 B 中搜索字符串 A 的 Knuth-Morris-Pratt 算法。如果找到该字符串,则返回字符串的第一个位置,否则返回 -1。但是现在我想计算字符串 B 中字符串 A 的总出现次数。
我尝试了一种简单的方法并且它正在工作,但这似乎并不有效,因为使用大字符串需要很多时间。
谁能帮我解决这个问题?我想要一种更有效的方式来使用 KMP。
这是我的测试。
//编辑:我解决了我的问题,我只需要正确阅读维基百科文章。
preprocessor - KMP 预处理函数
这是我在 ItoA 中看到的伪代码:
我的疑问是为什么在第 6 行我们这样做k = pi[k]
而不是k--
在我看来这应该是检查长度前缀的方式k
(因为如果P[k+1] != P[q]
这意味着k+1
无法实现也是后缀的长度前缀)也可以是后缀,那与 相比P[q]
,我也认为如果我们这样做,运行时间将保持不变。
string - 在 O(n) 中找到输入字符串的最小周期?
鉴于以下问题:
定义 :
让 S 是字母 Σ 上的字符串。
S'
是最小的周期S
ifS'
是最小的字符串,使得 :
S = (S')^k (S'')
,
S''
的前缀在哪里S
。如果没有这样的S'
存在,那么S
就不是周期性的。示例:
S = abcabcabcabca
。Thenabcabc
是一个周期 sinceS = abcabc abcabc a
,但最小的周期是abc
sinceS = abc abc abc abc a
。给出一个算法来找到输入字符串的最小周期
S
或声明它S
不是周期性的。提示:你可以这样做
O(n)
...
我的解决方案:我们使用 KMP ,它在 O(n) 中运行。
根据问题的定义,S = (S')^k (S''),那么我认为如果我们创建一个最短周期的自动机,并找到一种方法来找到最短周期,那么我就完成了.
问题是在哪里放置自动机的FAIL箭头......
任何想法将不胜感激,
问候
c++ - 为什么可以在 O(n) 时间内计算 KMP 失效函数?
维基百科声称可以在 O(n) 时间内计算出故障函数表。
让我们看看它的“规范”实现(在 C++ 中):
为什么它在 O(n) 时间内工作,即使有一个内部 while 循环?我对算法的分析不是很擅长,所以有人可以解释一下吗?
java - Java 中允许存在一种不匹配的 KMP 算法
我正在尝试解决HackerRank 挑战,但遇到了问题。显然,如果出于性能要求(我尝试过),O(n ^ 2)的蛮力解决方案将无法解决,因此我开始寻找更优雅的解决方案。那是我登陆KMP的时候。在本教程之后,我实现了它。
但是,挑战表明您实际上可以在字符串中存在一个不匹配,因此我尝试在我的代码中添加该功能。但是,我得到的结果不正确,我完全不知道为什么。有人可以看看我的解决方案并指出正确的方向吗?
algorithm - KMP(在维基百科上)中的“部分匹配”表(又名“失败函数”)
我正在阅读维基百科上的KMP 算法。“建表算法的伪代码描述”部分中有一行代码让我感到困惑:let cnd ← T[cnd]
它有一条评论:(second case: it doesn't, but we can fall back)
,我知道我们可以后退,但为什么是 T[cnd],有原因吗?因为它真的让我很困惑。
这是建表算法的完整伪代码:
java - 为什么 String.indexOf() 不使用 KMP?
我阅读了的源代码,java.lang.String
我惊讶地发现String.indexof()
不使用Knuth-Morris-Pratt 算法?众所周知,KMP 更有效。那么为什么不使用它String.indexOf()
呢?
我周围有人告诉我,对于短字符串,KMP 已经足够了,但是如果您需要性能并且打算使用大字符串,那么它不是一个好的选择。不过他没有告诉我细节。
所以,这是我的问题:
- 为什么我们不使用 KMP
String.indexOf()
呢? - 为什么 KMP 不是大字符串的好选择?
java - KMP DFA 前缀函数
我被要求了解 KMP DFA,而我在书中发现的就是这种实现,但我们的讲师一直称之为“前缀函数”。我真的不明白这个功能是哪一部分,有人可以给我解释一下吗?很抱歉,如果有人问过这个问题,但我找不到。