问题标签 [knuth-morris-pratt]

我指的是“Sedgewick & Wyane 的算法第四版”字符串匹配第 5 章。

给定的算法是 KMP 子字符串搜索，它从模式状态构建 DFA。我了解构建 DFA 的算法，代码如下：

我无法得到以下行： x = dfa[pat.charAt(j)][x]; // Update restart state.

我知道这个值是通过在部分构建 DFA 中提供 pat[1..j-1] 来实现的，但无法获得该代码，它是如何实现这一点的。

我也明白 x 是模式的最长前缀的长度也是后缀。

我见过许多其他相关问题，但这些问题与理解算法本身有关。

我需要了解如何x = dfa[pat.charAt(j)][x]; // Update restart state.模拟重启状态。

我注意到 KMP 算法在发现 Haystack[a] 和 Needle[b] 不匹配时只是参考故障函数，但它从不查看 Needle[b] 是什么。如果我们考虑 Needle[b] 是什么，是否有可能使 KMP 更快？

我正在研究我的竞争性编码技能，我遇到了一篇文章，用于计算字符串中每个前缀的出现次数。这是问题陈述给定一个长度为 n 的字符串 s。在问题的第一个变体中，我们要计算每个前缀 s[0…i] 在同一字符串中出现的次数。在问题的第二个变体中，给出了另一个字符串 t，我们想要计算每个前缀 s[0…i] 在 t 中出现的次数。我找到了解决方案。

代码：

据我所知前缀是什么，我无法完全理解问题陈述：

例如： string: geekforgeek 前缀为：{g,ge,gee,geek,geekf,geekfo,geekfor,geekforg,geekforge,geekforgee} 作为正确的前缀。有人可以帮我这个问题试图计算什么，因为只有这些是出现一次的可用前缀。提前致谢。

虽然到处都提到我们在计算 KMP 的 LPS 时只回溯内循环中增加的数量，但不清楚为什么整体复杂度为 O(length(pat))。

我正在阅读有关KMP 子字符串搜索算法的信息，并且我在网上找到的示例使用一维表来构建前缀信息表。
我还阅读了 Sedgewick 的解释，他使用二维数组来构建表格并明确指出 KMP 的空间复杂度O(RM)是R字母大小和M模式大小，而在其他任何地方都表示空间复杂度只是O(M + N)即要处理的文本和图案大小本身。
所以我对差异感到困惑。是否有多种 KMP 算法方法？他们有不同的范围吗？或者我错过了什么？
如果一维也能解决子串问题，为什么还需要二维呢？

当我们使用 Knuth-Morris-Pratt 算法时，这是在 Scheme 中计算失败函数（我们必须返回多少步）的代码：

但我不明白什么时候的部分k > 0。有人可以解释一下吗？

我想在 prolog 中创建 KMP 并开始像这样工作。不幸的是，我无法创建 Prolog 所需的前缀表？考虑到 prolog 是一种逻辑语言，我做得对吗？

需要澄清 KMP 算法的最佳时间复杂度和最差时间复杂度。令我困惑的是 O(n) 的最差搜索时间复杂度。网上看了下才明白是有两个索引。一个索引 i 用于文本，另一个索引 j 用于模式。而且我们不会减少文本索引 i。但是当存在不匹配且 j 值大于 0 时，我们会减少模式索引 j。在这种情况下，i 保持不变。那么最坏的时间复杂度怎么可能是 O(n) 呢？它应该比 O(mn) 更多。对于 i 的特定值，我们可以对 j 进行多次迭代。

还有什么是最好的情况？它与最坏的情况不同吗？我正在寻找简单的解释，因为我已经阅读了不同的教程。

我正在查看Leetcode 问题 459：

459. 重复子串模式

给定一个非空字符串，检查它是否可以通过获取它的子字符串并将子字符串的多个副本附加在一起来构造。您可以假设给定的字符串仅由小写英文字母组成，并且其长度不会超过 10000。

令 N 为字符串长度，L 为字符串最长真后缀的长度，如果 L 不为 0，且 N%(NL) 为零，则 s.substr(0, NL) 为重复组合子串。我理解这个说法。但是，我无法弄清楚相反的方向，即如果字符串是由重复的组合子字符串组成的，假设它的最短长度是K，那么字符串的最长正确后缀的长度是NK。有人可以提供一个通用的证明吗？

有人可以建议我如何制作在模式文本中包含“空白字母”的 Knuth–Morris–Pratt 算法吗？在输入时，您会得到模式和文本，模式在哪里？字符可以代表每一个字母。