Are these real string-search algorithms?

Yes — real Knuth-Morris-Pratt and Boyer-Moore implementations, each finding every true match in the text.

Why does Boyer-Moore often finish faster?

Its real mismatch-based skips can jump past several characters at once, while KMP advances more incrementally.

No — it is a pure local computation.

Yes — free, no download, in your browser.

Which is faster, KMP or Boyer-Moore?

Boyer-Moore is usually faster in practice when the pattern is long, because it can skip ahead. KMP has a simple linear guarantee and reads each text character in order without backing up.

Why does Boyer-Moore compare from the end?

A mismatch at the last character often rules out many alignments at once, since the text character may not appear anywhere in the pattern. That allows a large jump.

Do real programs use these algorithms?

Yes, in some form. GNU grep has been reported to use Boyer-Moore, and simplified variants such as Boyer-Moore-Horspool trade some of its skipping power for simpler code.

String Search Race Screensaver

The String Search Race screensaver runs real Knuth-Morris-Pratt and Boyer-Moore algorithms side by side, hunting for a pattern in the same live text. It is free, runs in your browser, and ESC exits.

How the String Search Race screensaver works

The saver picks a real short pattern and searches for it in a longer block of text using two real, distinct algorithms at once.

Knuth-Morris-Pratt uses a real precomputed failure table to skip ahead without ever re-checking characters it has already matched.

Boyer-Moore instead compares from the end of the pattern and uses real mismatch information to skip ahead by more than one character at a time.

Once both algorithms finish scanning the text, every real match found is highlighted, then a fresh pattern and text begin.

Two clever ways to find a needle in text

Searching for a short pattern in a longer text sounds trivial: slide the pattern along and compare at each position. The naive approach can be slow because after a failed match it starts over, throwing away what it learned. Two classic algorithms avoid that waste.

Knuth-Morris-Pratt was conceived by James Morris and independently found by Donald Knuth, with Vaughan Pratt; the three published it jointly in 1977. It precomputes how much of the pattern overlaps with its own beginning, and after a mismatch uses that table to resume without moving backwards in the text. Matching takes time proportional to the text length, with preprocessing proportional to the pattern length. Boyer-Moore, by Robert Boyer and J Strother Moore, also appeared in 1977. It compares from the right end of the pattern and uses the mismatching character to jump forward, sometimes by the whole pattern length.

Because Boyer-Moore preprocesses only the pattern and skips text, it tends to run faster as the pattern gets longer, and simplified variants such as Boyer-Moore-Horspool are common. GNU grep has been described as using Boyer-Moore. KMP's text pointer never moves backwards, which makes it a natural fit when input arrives as a stream.

A worked example

Boyer-Moore often leaps several characters ahead after a mismatch near the end of the pattern, while KMP advances more steadily using its real failure-table skips — both still landing on the same true matches.

Settings & tips

Accent recolours the pattern under comparison.
Both algorithms are real, correct, unmodified implementations.
A fresh pattern and text generate automatically once the scan finishes.

Frequently asked questions

Are these real string-search algorithms?: Yes — real Knuth-Morris-Pratt and Boyer-Moore implementations, each finding every true match in the text.
Why does Boyer-Moore often finish faster?: Its real mismatch-based skips can jump past several characters at once, while KMP advances more incrementally.
Is a key needed?: No — it is a pure local computation.
Is it free?: Yes — free, no download, in your browser.
Which is faster, KMP or Boyer-Moore?: Boyer-Moore is usually faster in practice when the pattern is long, because it can skip ahead. KMP has a simple linear guarantee and reads each text character in order without backing up.
Why does Boyer-Moore compare from the end?: A mismatch at the last character often rules out many alignments at once, since the text character may not appear anywhere in the pattern. That allows a large jump.
Do real programs use these algorithms?: Yes, in some form. GNU grep has been reported to use Boyer-Moore, and simplified variants such as Boyer-Moore-Horspool trade some of its skipping power for simpler code.

← All Science & Research screensavers