String matching
Every algorithm here is a different answer to one question: after a mismatch, how far can I safely jump? They run on text you choose and record every comparison they make, so you can watch the pattern slide, watch the table that decides how far it slides being built, and count what each of them actually cost.
6 algorithms
- Naive searchMove one. Always.Tries the pattern at every position in turn, comparing from the left until something disagrees, then moves along by exactly one character. Remembers nothing.O(n + m)O(n · m) worstO(1) space
- Knuth-Morris-PrattMove by whatever the part that already matched tells you.Precomputes, for every prefix of the pattern, the longest proper prefix that is also a suffix of it — and then searches without ever moving the text pointer backwards.O(n + m)O(n + m) worstO(m) space
- Boyer-Moore-HorspoolMove so the offending character lands where it belongs.Compares the pattern from its right-hand end, and on a mismatch jumps so that the text character under the pattern end lines up with its last occurrence in the pattern.O(n)O(n · m) worstO(alphabet) space
- Boyer-MooreAsk two rules how far is safe, and take the larger answer.Two independent rules — the bad character that stopped the match, and the good suffix that had already matched — consulted together, taking whichever says the larger jump.O(n)O(n · m) worstO(m + alphabet) space
- Rabin-KarpDo not jump at all — compare a number, and verify every hit.Compares a number instead of a string: one rolling hash per window, and every hash match checked character by character, because a hash match is a candidate rather than an answer.O(n + m)O(n · m) worstO(1) space
- The Z-algorithmReuse the answer already known for the window you are inside.Computes, for every position of the pattern joined to the text, how much of the whole string’s start repeats there — reusing a window of already-known answers rather than re-comparing.O(n + m)O(n + m) worstO(n + m) space
Nothing matches that. Clear the filter to see all 6.
Sorting and searching live next door in AlgoLab, and the call stack inRecursion.