Knuth Pratt算法DFA基于？

Question

我想学习Knuth Pratt算法是如何工作的。我看了普林斯顿大学https://www.youtube.com/watch?v=iZ93Unvxwtw的这篇教程。在这个视频中，他们使用一个表格，其中包含字母表的长度=行数和模式的长度=列数。将表作为DFA查看，DFA用于检测文本中的模式。我认为这种方法很有趣，但是Wikipedia说Knuth Pratt算法使用前缀表，前缀的长度只有一行。两者都是工作的，两者都是O(n+m)在速度的温度(n是文本的长度，m是模式的长度)。但是DFA版本需要更多的空间。但问题是哪一个是真正的Knuth Pratt算法，哪个是微分？

Answer 1

真正的(根据我所见过的大多数定义)是来自维基百科。将其实现为DFA的想法可能来自于Knuth Pratt算法是Aho-Corasick自动机的一个特例(它可以在trie上操作，而不仅仅是一个字符串)，它通常是以这种方式实现的(因为前缀表对它来说还不够)。