KMP - The optimal string matching algorithm

[@ComputerBread]

Hello everyone! I hope you will enjoy this video! In the previous video, we built a DFA to find a pattern in a text. The KMP algorithm reduces the memory usage of this DFA by introducing the idea of "failure links". Failure links, also called suffix links, appear in other algorithms that we will discover in future videos! (Check description for videos & code links)

[@mateusvmv]

Looks like an Aho-Corasick for a single pattern

[@ComputerBread]

It is, Aho-Corasick can be seen as an extension of the KMP algorithm. I actually made this video to introduce the concept of "failure links", so I can explain the Aho-Corasick algorithm more easily. Aho-Corasick = trie + failure links + output links

[@hwstar9416]

is this really optimal in practice? I feel like allocating a new buffer would cause this algorithm to perform worse in some cases.

[@ComputerBread]

Asymptotically yes, in practice probably not, I've read somewhere (can't remember where) that Boyer-Moore is 25% faster on english text. In some cases, brute force can probably be faster.