问题标签 [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.
algorithm - 哪种模式更适合 KMP，为什么？
在以下 2 种模式中，哪种模式在 KMP 算法方面表现更好？
模式 1 = PQRSTUV 模式 2 = PPPPPPP
string - 在构建部分匹配表时，KMP 中的第二个 while 循环的目的是什么？
为 KMP 构建部分匹配表时：
为什么第二个 while 循环不是有条件的呢？如：
在我尝试过的大多数示例中，此语句用于在不匹配时将 j 重置为 -1，因此当下一次迭代到来时，我们将字符串的第一个字符 (P[j]) 与该字符进行比较在位置 i (P[i])。
f# - 如果我在前两个索引处使用具有相同字符的模式，则 F 锐利 KMP 算法卡在第一个 while 循环中
我正在玩 f sharp 中的 KMP 算法。虽然它适用于 "ATAT" 之类的模式（结果将是 [|0; 0; 1; 2;|]），但当字符串的前 2 个字符相同且第三个字符是另一个时，第一个 while 循环进入死锁，例如“AAT”。
我明白为什么：首先，i 递增到 1。现在 while 循环的第一个条件为真，而第二个条件也为真，因为“A”<>“T”。现在它将 i 设置为 prefixtable.[!i]，它又是 1，我们开始吧。
你们能给我一个关于如何解决这个问题的提示吗？
string - Knuth-Morris-Pratt (KMP) 和使用 Ukkonen 算法的后缀树之间的时间复杂度差异。
是否可以使用 Ukkonen 算法通过 KMP 和后缀树找到最长公共子串、最长回文子串、最长重复子串、搜索所有模式和子串检查？如果是，那么我应该使用哪一个，因为这两种算法都具有线性时间复杂度？
algorithm - 使用 KMP 算法在字符串匹配中处理通配符“*”运算符？
当要匹配的模式包含通配符时，我应该如何使用KMP *- Algorithm处理这种情况？AB*CABEFGCS*EFG
算法中的哪些修改可以解决这个问题？
algorithm - KMP算法最坏情况分析
我无法理解 KMP 如何保持 O(m+n)。我正在“aaaaaaaaaa ...”中寻找模式“aaaab”。
- 模式：aaaab（长度 n）
- 字符串：aaaaaaaaaa...（长度 m）
那么前缀表将是
aaaab
01230
每次在“b”上发生不匹配时，它的前缀长度始终为 0。所以模式只向右移动了一步。
啊啊啊啊……
aaaab
啊啊啊啊……
_aaaab
啊啊啊啊……
__aaaab
对于每次试验，我都需要比较完整的 n 次，因为不匹配发生在最后一个“b”。因此它仍然需要 O(m*n) 比较。
谁能解释一下 KMP 是如何为我得到 O(m+n) 的？提前致谢。
python - 我在 python 中的计算前缀函数实现给出了错误的结果
我在 Python 中实现了 Compute-Prefix-Function，但它给了我错误的结果（我是 python 的初学者） 有人可以帮我与伪代码相比，我的实现有什么问题吗？
结果是：[0, 0, 0, 1, 2, 0, 0]。但正确的结果必须是：[0, 0, 1, 2, 3, 1, 1]
此处提供了pseudoc 代码。它在第 7 页
algorithm - 计算 KMP 实现中的下一个前缀索引
我已经阅读了许多不同的 KMP 实现，并不能完全弄清楚它们都共享的一个方面。
当他们计算也是后缀数组（lps）的最长前缀时。如果字符在特定迭代中测试的索引处不匹配，并且前缀的索引不为0。前缀的索引设置为
索引 = lps[索引 - 1];
这是一个例子
是否存在index = lps[index-1]不等于的情况
指数 - ;
string - Knuth–Morris–Pratt algorithm: border array
Here is a pseudo code for computing the border array in KMP.
p is the pattern
I can execute the following pseudo code to compute the border array but the problem I am having right now is that I don't really understand the border array meaning how to interpret it.
For instance if the pattern does not equal at position (i+1) and (j-1) the variable i is set to border[i+1]. Why is that for example?
I realized the missing understanding when I tried to answer the question that three consecutive entries in a border array cannot differ by one from its predecessor. E.g. border[10]=3, border[11]=2, border[12]=1
I would appreciate a good explanation in order to get a better understanding.
string - 什么时候使用 KMP 算法比较好？
我知道 KMP 算法取决于辅助数组，其中有类似于后缀的前缀。当上述条件不满足时，它不会有效，因为辅助数组中包含全零。运行时间会是 O(m + n) 吗？如果我是对的，在这种情况下什么是更好的子字符串算法？