问题标签 [knuth-morris-pratt]

我熟悉这两种算法：Knuth Morris Pratt 和 Boyer moore。

给定一个由包含大量字母的字母组成的字符串 P。哪个算法更好用？

给定一个带有二进制字母（0 或 1）的字符串 P。哪个算法更好用？

我从 Wikipedia 检查了KMP 建表算法，但我不明白 while 循环的第二种情况背后的逻辑

我尝试使用此算法构建一个表，并且效果很好。我知道这cnd ← T[cnd]有助于找到合适的后缀长度。我不明白的是“如何”做到这一点？

一个例子的解释会很好。

谢谢！

编辑：我刚刚发现我的问题与此处的问题重复：KMP 中的“部分匹配”表（又名“失败函数”）（在维基百科上）

我想我现在得到了答案。不过，再做一个解释会很有帮助。谢谢！

我正在尝试实现 KMP 算法。我的算法适用于以下示例

• 文字：121121
• 图案：121
• 结果：1,4

但是当 Text 为 12121 并且 pattern 与上面相同时，结果只是： 1.我不知道这是算法的问题还是我的实现的问题？

其他示例：

• 文字：1111111111
• 图案：111
• 结果：1,4,7

我的代码是：

Knuth-Morris-Pratt 算法旨在查找字符串中子字符串的第一次（也可能是下一次）出现。由于子字符串可以包含重复部分，因此它使用某种回溯机制。这是伪代码中的算法：

（来自维基百科）。用W子串和S要搜索的字符串，都是从零开始的数组。

if我对算法中的最后一个子句有一个疑问：if T[i] > -1 then基于T-vector 构造算法，似乎只有T[i]index 小于零i = 0。在这种情况下，可以对索引执行更快的“检查”（数组访问是一条附加指令，特别是如果考虑到可能的缓存错误），就像 assignment 一样i ← 0。

的构造T由以下算法完成：

（来自维基百科）。

现在可以看到算法只写入0或cndto的值T。对于第一种类型的赋值，这个陈述是平凡的。对于第二种情况，它取决于 的值cmd。

现在唯一cmd可以减少的方法是通过第二种情况(*)，在这种情况下， cmd 将变得越来越小，直到它的值为零或更小。但由于cmd从数组的已初始化部分获取值，因此可以是0或-1。如果cmd确实是-1，这将导致T[pos]设置为，0因为在设置值之前有一个增量。万一cmd为零，则完全没有问题。

因此，更有效的算法将是：

这个说法正确吗？如果没有，你能给出一个子字符串，其中两个或多个-1s 出现在T-array 中吗？

我正在阅读关于 KMP 算法的 topcoder 教程，但我无法理解文本的以下部分：

给定一个字符串（一个很长的字符串），找到它的所有正确的后缀，这些后缀也是它的前缀。我们所要做的只是计算给定字符串的“失败函数”，并使用其中存储的信息来打印答案。

我知道如何计算故障函数，对于字符串abacababa，我得到以下数组[0, 0, 1, 0, 1, 2, 3, 2, 3]。问题是我无法弄清楚它如何帮助我找到

它的所有正确的后缀也是它的前缀

根据我的理解假设是aand aba。

我正在使用最后一个函数进行 KMP 字符串搜索的算法......一切似乎都运行良好，除了我认为它不匹配的时候？我没有通过名为 testKMPNotThere 的 JUnit 测试。它断言当在文本中找不到模式时返回的列表应该为空...

所以它应该返回一个 [] 列表，但由于某种原因它返回 [1] 之一.. 我不知道为什么它在找不到模式时添加 1..

这是我的代码-

让

knuth morris pratt 算法中字符串（T）中的特定字符与模式（P）进行比较的最大次数是多少？

如何及时从字符串中删除模式 p 的所有出现O(s+p)？

就像如果

那么结果字符串应该只有 B

所以对于下面的子字符串

哪个是前缀函数？我和我的一个朋友计算了它，我们得到了不同的结果，我的是：

和他的：

如果我错了，那是为什么呢？

我指的是 Sedgewick 的“算法”一书中（第 4 版）中用于子串搜索的 Knuth-Morris-Pratt (KMP) 算法的大纲。

KMP 算法在基于确定性有限自动机 (DFA) 的子串搜索中使用备份。我了解 DFA 如何进入算法，但是我不了解如何构造DFA，这是通过以下代码片段完成的：

其中M是图案的长度pat和R字母的大小。该charAt()函数返回相应位置的字符的整数值。

有人可以解释这段代码以什么方式构建 dfa 吗？我迷失在内部 for 循环的实际直观含义中。