5

我想了解 Knuth-Morris-Pratt 算法的工作原理。我从普林斯顿大学https://www.youtube.com/watch?v=iZ93Unvxwtw观看了本教程。在这个视频中，他们使用了一个表格，字母的长度 = 行数，图案的长度 = 列数。将表格视为 DFA，用于检测文本中的模式。我认为这种方法很有趣，但维基百科说 Knuth-Morris-Pratt 算法使用前缀表，前缀长度只有一行。两者都有效，并且在速度方面都是 O(n+m)（n 是文本的长度，m 是模式的长度）。但 DFA 版本需要更多空间。但问题是哪个是真正的 Knuth-Morris-Pratt 算法，哪个是微分？

4

1 回答 1

3

真正的（根据我见过的最多定义）是来自维基百科的。将其实现为 DFA 的想法可能来自这样一个事实，即 Knuth-Morris-Pratt 算法是 Aho-Corasick 自动机的一个特例（它可以在 trie 上运行，而不仅仅是一个字符串），通常以这种方式实现（因为前缀表是不够的）。

于 2014-10-04T18:50:40.423 回答