I want to learn how the Knuth–Morris–Pratt algorithm works. I watched this tutorial form the Princeton University https://www.youtube.com/watch?v=iZ93Unvxwtw . In this Video they use a table, with length of the alphabet = number of lines and length of the Pattern =number of columns. The see the table as an DFA which is used to detect the pattern in the text. I think this approach is interesting but Wikipedia says that the Knuth–Morris–Pratt algorithm uses a prefix table with only one line for the length of the prefixes. Both works and both is O(n+m) in therms of speed(n is the length of the text and m is the length of the pattern). But the DFA Version needs more Space. But the Question is which is the real Knuth–Morris–Pratt algorithm and which is a differentiation?
The real one(according to the most definition I have seen) is the one from Wikipedia. The idea of implementing it as a DFA probably comes from the fact that Knuth-Morris-Pratt algorithms is a special case of the Aho-Corasick automaton(it can operate on a trie, not just one string), which is usually implemented this way(because prefix table is not sufficient for it).