问题标签 [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.
string - 除了 Knuth-Morris-Pratt、Rabin-Karp 等，还有哪些可用的字符串匹配算法？
除了 Knuth-Morris-Pratt、Rabin-Karp 等，还有哪些可用的字符串匹配算法？
algorithm - 搜索二维矩阵以寻找另一个较小尺寸的矩阵的有效方法
我知道 KMP ( Knuth–Morris–Pratt ) 用于一维搜索。它可以应用于二维数据数组吗？还是有更高级的？
string - KMP模式匹配算法背后的理论是什么？
KMP模式匹配算法的理论基础是什么？
我了解算法本身，但不明白 Knuth、Morris 和 Pratt 是如何发明这种算法的。
有数学证明吗？
请问可以给个链接吗？
string - 当目标是找到某个字符串的所有出现时，KMP 的最坏情况复杂度是多少？
我还想知道哪种算法在查找另一个字符串中所有出现的字符串时具有最坏情况的复杂性。似乎 Boyer–Moore 的算法具有线性时间复杂度。
string - 有没有关于如何实现二维 KMP 的论文或解释？
我尝试使用 Aho-Corasick 和一维 KMP 的组合来解决二维搜索问题，但是，我仍然需要更快的东西。
详细地说，我有一个大小为 n1*n2 的字符矩阵 A ，我希望找到所有出现的大小为 m1*m2 的较小矩阵 B 并且我希望它在 O(n1*n2+m1*m2) 中，如果可能的。
例如：
和
该算法应该返回例如匹配左上角的索引，在这种情况下应该返回 (0,1) 和 (0,3)。请注意，事件可能重叠。
string - Knuth-Morris-Pratt 算法中的模式前缀函数计算
给定模式的前缀功能是否有可能具有这样的东西，
0 0 1 2 3 0 1 2 3 4 5 3 4 56 7 0 1 2
在 4 5 之后的上述前缀函数中，是否只有 6 或 0 的可能性？如果在 4 5 之后有可能出现例如 3（小于 5 且大于 0），如上述那样，那么模式应该如何。
我只能想到类似于这个的模式，
谢谢。
string - 匹配一个或零个不匹配的字符串模式
给定一个要匹配的字符串和一个模式，如何有效地找到零个或一个不匹配的匹配项。
我试图修改 KMP 算法，但我不确定该方法。
请给我一个想法来解决这个问题。
谢谢。
java - Java 搜索字符串(kmp)
我想搜索字符串 b 中有多少次出现的字符串（比如说 a）。我想过实现 Knuth-Morris-Pratt 算法，但我更喜欢内置的 java 函数。有没有这样的功能？我希望该函数尽可能地具有最低的复杂性，因为我多次使用它。
c - 纯 C 中的 Knuth-Morris-Pratt 实现
我有下一个 KMP 实现：
你可以在这里测试它：http: //liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80
它适用于小字符串，并且我已经用大循环对其进行了测试，这样一切都很好。
但是，如果我将要搜索的子字符串和完整字符串更改为：
只有在第一次尝试之后，这个实现才会失败......
拜托，您能帮我修复 KMP 的实现，以使算法与字符串中的此类数据一起工作...
string - KMP算法中使用的Failure函数是如何工作的？
我已经尽力阅读了大部分关于这方面的文献，但仍然不了解 KMP 算法中使用的故障函数是如何构造的。我主要指的是大多数人认为优秀的http://community.topcoder.com/tc ?module=Static&d1=tutorials&d2=stringSearching 教程。但是，我仍然没有理解它。如果您能不厌其烦地给我一个更简单易懂的解释，我将不胜感激。