个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
26
4
我想了解 Knuth–Morris–Pratt 算法的工作原理。我从普林斯顿大学观看了这个教程 https://www.youtube.com/watch?v=iZ93Unvxwtw .在此视频中，他们使用了一个表格，字母表的长度 = 行数，模式长度 = 列数。将表格视为 DFA，用于检测文本中的模式。我认为这种方法很有趣，但维基百科说 Knuth-Morris-Pratt 算法使用前缀表，其中只有一行用于前缀长度。两者都有效，并且都是 O(n+m) 速度热(n 是文本的长度，m 是模式的长度)。但 DFA 版本需要更多空间。但问题是哪个是真正的 Knuth–Morris–Pratt 算法，哪个是微分？
最佳答案
真正的(根据我看到的最多的定义)是来自维基百科的。将其实现为 DFA 的想法可能来自于 Knuth-Morris-Pratt 算法是 Aho-Corasick 自动机的一个特例(它可以在一个特里树上运行，而不仅仅是一个字符串)，通常以这种方式实现(因为前缀表不足以满足它)。
关于algorithm - Knuth-Morris-Pratt 算法基于 DFA `？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26195446/
26
4
0
我最近从 this 了解了 Pratt 解析器。优秀的文章，发现 Pratt 解析器比递归下降解析器更简单、更优雅。我试图找到更多关于它们如何与其他解析器类型进行比较的信息，但发现 Wikipedia
有谁知道或知道是否可以修改用于子字符串搜索的 KMP 算法以查找近似匹配而不是精确匹配？ 最佳答案 看看 Bitap algorithm . 关于algorithm - Knuth-Morris-Pr
我正在研究 KMP 算法，在这张幻灯片中，我下载了一个 powerpoint，它显示了一个由算法的失败数组制成的转换表。我无法理解它的正面或反面。与 DFM 相关的转换表究竟显示了什么？转换表在右上角
Knuth-Morris-Pratt algorithm旨在找到字符串中子字符串的第一次(可能是下一次)出现。由于 substring 可以包含重复部分，因此它使用了某种回溯机制。这是伪代码中的算法:
我一直在备考的时候遇到这个问题，请大家帮忙 For any alignment of pattern P and text T, suppose a mismatch occurs at P[i+1]
让 T:String P:pattern 在 knuth morris pratt 算法中，字符串 (T) 中的特定字符与模式 (P) 进行比较的最大次数是多少？ 最佳答案 |P|。这是一个例子: P
在 Knuth-Morris-Pratt 算法中，当“子串”单词是相同字母的序列时，例如。 “AAAAAAAA...”，故障表是这样的:“-1, 0, 1, 2, 3, 4, 5,...”。 这意味着
是否有可能在给定模式的前缀函数中有这样的东西， 0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2 在上面的前缀函数中，在 4 5 之后是否只有 6 或 0 的可能？如果在上面
所以对于下面的子串 1 2 3 4 5 6 7 8 9 10 11 a b c d a b c d a b x 什么是前缀函数？我和我的一个 friend 计算了它，我们得到了不同的结果，我的是:
我正在为参加的考试而学习，我正在研究 Knuth-Morris-Pratt 算法。考试要考的是Fail table和DFA construction。 DFA的构造我懂，但是fail表怎么制作我不是很
是 Knuth–Morris–Pratt algorithm 的解决方案: 干草堆:AAAAAAAAAA，针:AAA，即:3，正确吗？ 因为大海捞针中有 8 个 AAA 实例，但据我所知，knuth-
我创建了一个简单的 Knuth–Morris–Pratt algorithm 实现在斯卡拉。现在我想要花哨并以尾递归的方式做同样的事情。我的直觉告诉我这应该不会太难(表格和搜索部分)，但同样的感觉也告
我发现 Boost 实现了 KMP 算法，我想将它与 circular_buffer 一起使用，但我无法将其与组件相匹配。任何有 boost 经验的人都可以告诉我如何做到这一点。 最佳答案 您遇到了什
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题？ 更新问题，以便 editing this post 可以用事实和引用来回答它. 关闭 9 年前。 Improve
我试过做 Morris Pratt 表，代码基本上是 C 中的这个: void preMp(char *x, int m, int mpNext[]) { int i, j; i = 0; j = m
如果我们发现不匹配，我们可以在不比较的情况下猜测文本中的下一个字符是否不匹配， 文字: abacabba 图案:阿爸 现在，当它比较模式中的第二个“b”和文本中的第二个“a”时，存在不匹配，有什么方法
我正在实现支持通配符的 KMP 字节模式搜索。下面是生成前缀表的算法 WITHOUT 通配符: vector PrefixFunction(string S) { ve
我想了解 Knuth–Morris–Pratt 算法的工作原理。我从普林斯顿大学观看了这个教程 https://www.youtube.com/watch?v=iZ93Unvxwtw .在此视频中，他
有人能给我解释一下吗？我一直在阅读它，但仍然很难理解。 文本:ababdbaababa 图案: ababa ababa 的表是 -1 0 0 1 2。 我想我明白表格是如何构建的，但是，我不明白一旦发
我很难理解 Haskell 中 Knuth-Morris-Pratt 算法的这种实现。 http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Hask
我是一名优秀的程序员,十分优秀！