×
About Find in Text
Every Find box, search engine and spell checker has to answer the same question: where in this text does this pattern appear? Type or paste a text on the form (up to 20,000 letters), type what to find, and press RACE . Four tape readers search the same text side by side, one letter comparison per step each, so the one that compares fewest letters finishes first. STEP moves them all on one comparison; Space races or pauses, → steps. COPY LINK copies a link to the setup (the text too, when it's under 1,500 letters).
On each tape the brass reading head carries the pattern. The letter being compared lights up green (the same) or red (different); each letter the reader looks at gets a hole punched under it, so you can see which letters a method never looks at. A gold arrow shows each jump. Places where the pattern was found are boxed in blue. The tally slip counts the letters every method compares (Horspool's included) on your text.
THE STORY
This app grew from the Python script kmp_str_search.py , a short Knuth–Morris–Pratt search that returns True or False. It can give the wrong answer: after a mismatch where its failure value is 0 it moves on in the text but keeps its place in the pattern, so it says cat is in the cart (skipping the r) and misses ABBA in ABABBA . Its failure table also starts again from 0 instead of falling back (for AABAAA its last entry is 0, not 2). Its own two tests happen to pass. The version here is the textbook one.
Knuth–Morris–Pratt. James H. Morris found the method in 1970 while writing a text editor, and wrote it up with Vaughan Pratt; Donald Knuth reached the same idea independently from a theorem of Stephen Cook's about automata. The three published it together in 1977 as Fast pattern matching in strings . It never needs more than 2n comparisons for a text of n letters, and it never goes back in the text, which suits a tape that only runs one way.
Boyer–Moore. Robert S. Boyer and J Strother Moore published A fast string searching algorithm in 1977. Its surprise is to compare the pattern from its right-hand end: one letter that isn't in the pattern at all lets it jump the whole pattern length, so the longer the pattern, the fewer letters it reads. Nigel Horspool's 1980 version keeps only the simpler jump table and is often just as fast on everyday text. Search tools and text editors still use Boyer–Moore's ideas.
Rabin–Karp. Richard Karp and Michael Rabin published their method in 1987. It turns each window of text into a number (a hash) and only compares letters when the window's number equals the pattern's. The trick is that sliding the window on one letter updates the number in a couple of sums instead of starting again. It shines when looking for many patterns at once, as in plagiarism checkers.
HOW IT WORKS
Plain search puts the pattern at the first place, compares left to right until a letter differs, then moves on one place and starts again from the pattern's first letter. Usually it fails on the first letter or two, but on text like AAAA…AB with pattern AAAAAAB it compares nearly every letter of the pattern at every place: up to (n − m + 1) × m comparisons for a pattern of m letters.
Knuth–Morris–Pratt works out a failure table first: for each length of matched start, the longest piece at its end that is also a start of the pattern. After a mismatch those letters are already known to match the text, so the pattern slides on and carries on from there without reading any text letter twice except the one that failed.
Boyer–Moore takes the bigger of two jumps after a mismatch. The bad character rule slides the pattern until its last copy of the mismatched text letter lines up with it (or right past it, if the pattern doesn't have that letter). The good suffix rule uses the letters that did match: it slides until another copy of that ending, or a start of the pattern that matches its end, lines up. On text of A's with pattern AAAAAA, finding every match, it rereads the whole pattern at every place (n × m ); Zvi Galil's 1979 change fixes that and isn't used here. Horspool always jumps by the window's last letter only. Pick which one the third reader uses on its name plate.
Rabin–Karp here treats each letter as a number (its character code), reads a window as a number in base 256 and keeps only the remainder after dividing by 101. With a divisor that small, different windows often share a remainder, so you will see false alarms, where the letters then have to be checked and don't match. Real programs use a huge prime, often picked at random, so false alarms are rare. Each hash check counts as one step in the race.
Comparisons are counted, not timed: on a real computer the work per comparison differs by method, and for short texts the time is too small to see.
FURTHER WATCHING AND READING