4 ms·
Isn't the "homebrew" result at the end exactly the state machine from the DFA? It has been a while, but I remember KMP calculating a prefix table of some sort
by maweki 6y ago
Isn't the "homebrew" result at the end exactly the state machine from the DFA?
It has been a while, but I remember KMP calculating a prefix table of some sort beforehand, to skip the repeated checking on yet-unclear partial matches?
- Jtsummers 6y agoYes. The author discusses the relation between the homebrew solution and a DFA solution in part 2, and more about partial matches in part 3.
- thdc 6y agoYeah, back in university I've really only learned the version that is presented in part 3. I mean I feel like the prefix table is just a more succinct representation of the DFA but I do find it interesting to see one way that that approach could've been arrived at.