Clever Geek Handbook

Knuth-Morris-Pratt algorithm based on DFA?

I want to know how the Knuth-Morris-Pratt algorithm works. I was watching this tutorial from Princeton University https://www.youtube.com/watch?v=iZ93Unvxwtw . In this video they use a table with alphabet length = number of rows and length of Pattern = number of columns. See Table as DFA which is used for pattern detection in text. I think this approach is interesting, but Wikipedia says the Knuth-Morris-Pratt algorithm uses a single-row prefix table for the prefix length. Both works and both are O (n + m) in speed topics (n is text length and m is drawing length). But the DFA version needs more space. But the question is, is the real Knuth-Morris-Pratt algorithm and is it differentiation?

+3


source to share


1 answer


The real one (by the very definition I've seen) is the one from Wikipedia. The idea of ​​implementing this as a DFA probably comes from the fact that Knuth-Morris-Pratt algorithms are a special case of the Aho-Korasik automaton (it can run on a trie, not just one line), which is usually implemented this way (because for it's not enough prefix table).



+2


source






More articles:


All Articles