问题标签 [knuth-morris-pratt]

我需要将用户将搜索的产品名称与可用产品进行比较。我有存储在 MySQL 数据库中的产品名称。我正在收集所有名称，并在我的 java 服务启动时将其带到应用程序级别（java）。

现在我的字符串比较场景是这样的：

谁能建议在Java中哪种算法适合这个？还有一件事，将所有产品名称从 MySQL 带到应用程序级别（java）是正确的方法吗？或者我也可以在 MySQL 级别做吗？（PS：我不想在 MySQL 端使用 like 查询，因为它会很慢）

在 Knuth-Morris-Pratt 算法中，当“子串”词是相同字母的序列时，例如。“AAAAAAA...”，故障表是这样的：“-1, 0, 1, 2, 3, 4, 5,...”。

这意味着如果测试类似于“AAAAAAAB”，当我们到达“B”时，我们将返回 X 个字符并再次开始尝试匹配，尽管我们知道我们应该在 B 之后开始。

我错过了什么吗？

编辑（使示例具体）：

假设测试是：AAAAAAAABAAAAAAAAA，即 (8 As, B, 9 As)，而寻找的词是 AAAAAAAAA，即 (9 As)。

失败表将为：-1、0、1、2、3、4、5、6、7。

在某些时候它将是 m = 0，i = 8。这将失败，所以 m 将变为 m = m + i - T[8] = 0 + 8 - 7 => m = 1，而 i 将是 T[8 ] = 7。

这将再次失败，所以现在我们将有 m = 2、i = 6，然后是 m = 3、i = 7，等等。

有人可以帮我理解哪个更有效 strstr() 或 KMP，因为最近我在 SPOJ 上做一个问题，发现 strstr() 以某种方式比 KMP 更快。有人请解释这背后的奥秘。 .

我在备考时遇到这个问题，请大家帮忙

对于模式 P 和文本 T 的任意对齐，假设在 KMP 算法执行过程中 P[i+1] 和 T[k] 发生不匹配 KMP 执行过程中，T[k] 总共比较了多少次算法（SPi 未优化）

我遇到的可能解决方案是

1. i-SPi
2. SPI+1
3. 你
4. n-SPi

但在某些情况下它们都失败了，

Suppose I have a pattern P and some text T, and I want to find the largest prefix of P that matches a substring of T. Is it possible to modify the KMP algorithm to do such an operation? (If I remember correctly, the KMP algorithm does partial matches, but I am interested in the longest possible match).

我想在字符串 S 中找到与正则表达式 R 匹配的所有子字符串。正则表达式只能包含“。” 和符号（其中“.”表示任何符号）。我正在尝试使用 KMP 来解决这个问题：

1) 构建字符串 T = R + '#' + S （'#' 在这里是分隔符）

2) 计算前缀函数。对于 T

3) 对于 pi（T 的前缀函数）检查 '#' 之后的位置，其中 pi[i] == len(S)。在这些位置寻找子串结束。

但是前缀功能。不能在带有 '.' 的字符串上正常工作 我的前缀函数代码：

它在测试 S="abab", T="a." 时失败。

我知道可以使用 KMP 来解决这个问题，你能告诉我怎么做吗？

我正在准备考试，并且正在研究 Knuth-Morris-Pratt 算法。考试内容是 Fail 表和 DFA 构造。我了解 DFA 构造，但我并不真正了解如何制作失败表。

如果我有一个模式“abababc”的例子，我该如何构建一个失败表？解决方案是：

失败表：

0 1 2 3 4 5 6 7

0 0 0 1 2 3 4 0

但我怎么得到呢？没有代码只是解释如何获得它是必要的。

我使用以下字母生成了一个字符串。 {A,C,G,T}. 我的字符串包含超过 10000 个字符。我正在其中搜索以下模式。

• ATGGA
• TGGAC
• CCGT

我已要求使用具有O(m+n)运行时间的字符串匹配算法。

两者KMP and Rabin-Karp algorithms都有这个运行时间。在这种情况下，最合适的算法（在 Rabin-Carp 和 KMP 之间）是什么？

我在 Scala 中创建了Knuth-Morris-Pratt 算法的简单实现。现在我想变得花哨并以尾递归的方式做同样的事情。我的直觉告诉我这不应该太难（表格和搜索部分），但同样的感觉也告诉我，这一定是有人已经完成了，可能比我更聪明。因此问题。你知道 Knuth-Morris-Pratt 算法的任何尾递归实现吗？

这是我的申请

“Textform”，从搜索框中获取值。

“listKamus”，从数组中取值。然后“玩家名称”，将其值更改为字符串。

"KMP.knutMorris(textform, playerName)", 发送 textform, playerName 值到 knutMorris 类

主要课程

KMP 级

我希望人们在搜索框中键入时显示正确的数组列表。

我认为错误之一在这里

主要课程

或者在这里

KMP 级

谁能告诉我如何解决这个问题？