KMP - The optimal string matching algorithm
Вставка
- Опубліковано 16 чер 2024
- Hello, today, we learn about the Knuth-Morris-Pratt exact string matching algorithm. It has the optimal worst-case time complexity of Big-O of m+n. Where m is the length of the pattern and n is the length of the text. And it requires a reasonable extra space of Big-theta of m.
This video is based on the previous video in which we constructed a Deterministic Finite Automaton (DFA) to find a pattern in a text. It extends that idea by introducing the idea of "failure links".
In this video, we implement the KMP algorithm in JavaScript.
We also cover the idea of borders!
Previous video about DFA: • The most fundamental s...
Video about the Boyer-Moore algorithm: • The algorithm behind C...
Playlist about string algo: • Characters & Strings
Source code: github.com/ComputerBread/algo...
Support me: ko-fi.com/computerbread
Cheatcheet/mindmap: ko-fi.com/s/34966c8fb1
Twitter: / computerbread
Subscribe: / @computerbread
2nd Channel: @computerbreadboard
Chapters
00:00 Introduction
00:46 Failure Links
02:51 KMP implementation
04:25 Building failure links
07:38 Failure links implementation
12:45 Conclusion
Banger to listen to while studying: • Mozart: Die Entführung...
Helpful resources:
- www.wild-inter.net/teaching/c... - Наука та технологія
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)
Looks like an Aho-Corasick for a single pattern
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
is this really optimal in practice? I feel like allocating a new buffer would cause this algorithm to perform worse in some cases.
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.