Ask*_*ker 5 algorithm knuth dfa
我想了解 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法的工作原理。我在普林斯顿大学观看了本教程https://www.youtube.com/watch?v=iZ93Unvxwtw。在此视频中，他们使用一个表格，其中字母表长度 = 行数，模式长度 = 列数。将该表视为 DFA，用于检测文本中的模式。我认为这种方法很有趣，但维基百科说 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法使用一个前缀表，其中只有一行前缀的长度。两者都有效，并且两者的速度都是 O(n+m)（n 是文本的长度，m 是模式的长度）。但DFA版本需要更多空间。但问题是哪个是真正的 Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法，哪个是微分？
\n真正的（根据我见过的最多的定义）是来自维基百科的。将其实现为 DFA 的想法可能来自这样一个事实：Knuth-Morris-Pratt 算法是 Aho-Corasick 自动机的一种特殊情况（它可以在 trie 上操作，而不仅仅是一个字符串），通常以这种方式实现（因为前缀表不足以满足它）。