我想了解Knuth-Morris-Pratt算法是如何工作的。我在普林斯顿大学 https://www.youtube.com/watch?v=iZ93Unvxwtw 上观看了本教程。在此视频中，他们使用一个表格，字母表的长度=行数，模式的长度=列数。将表格视为用于检测文本中模式的 DFA。我认为这种方法很有趣，但维基百科说 Knuth-Morris-Pratt 算法使用前缀表，前缀长度只有一行。两者都有效，并且都是速度温度的O(n+m((n是文本的长度，m是图案的长度(。但是DFA版本需要更多的空间。但问题是哪个是真正的高德纳-莫里斯-普拉特算法，哪个是微分？
真正的一个(根据我见过的大多数定义(是来自维基百科的那个。将其实现为 DFA 的想法可能来自这样一个事实，即 Knuth-Morris-Pratt 算法是 Aho-Corasick 自动机的一个特例(它可以对一个 trie 进行操作，而不仅仅是一个字符串(，通常以这种方式实现(因为前缀表不足以满足它(。