Pattern Matching: Finding a Word Inside a Text, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.9 Free with a free account

Pattern Matching: Finding a Word Inside a Text

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.9 · lesson 75 of 8710 min · free with a free account

← Strings: Why Text Needs Its Own Data HandlingNext lesson: Tries: Storing Vocabularies in Prefix Trees →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Brute force, Rabin-Karp, KMP, and Horspool for finding a pattern.

  • Count the character comparisons of brute-force matching and identify its worst case
  • Explain Rabin-Karp's rolling hash and why hash matches are confirmed character by character
  • Build the KMP failure function and explain why KMP never rereads the text
  • Build a Horspool shift table and choose a matcher for a given task

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,335 words). Read along, or search it.

Opening Question

Searching a Million-Character Log

You search a log of one million characters for an eight-letter code. The obvious method makes about a million character comparisons. A cleverer method needs fewer than 150,000. And on unlucky input, the obvious method can need nearly a thousand comparisons per character. Where does a gap like that come from? We'll build four ways to find a pattern in a text, and count what each one costs.

The Problem

Shifts, Occurrences, and Comparisons

The text has n characters, and the pattern has m. A shift is a position where the pattern is placed. An occurrence is a shift where all m characters match. We report every occurrence, overlapping ones too. And we judge each method by its character comparisons, where nearly all the time goes. Java's String.indexOf already does this job. The point is to see how it can be done, and what that costs.

Brute Force

Try Every Shift and Forget Partial Matches

Brute force places the pattern at shift zero, and compares character by character. At the first mismatch, it gives up, and tries the next shift. Here the pattern is a b a b d, in a fifteen-letter text. Run it. Most shifts fail at once, for one comparison. But shifts zero and eight match four characters before failing, and that work is simply forgotten. It finds the one match, at shift 10, after 27 comparisons.

Worst Case

A Text Built to Hurt Brute Force

If the pattern's first character almost never matches, each shift costs one comparison: about n in all. The worst case is the opposite. Take a text of 10,000 a's, and a pattern of 99 a's followed by a b. Every shift matches 99 characters, then fails at the very end. Run it. 990,100 comparisons: 9,901 shifts, times 100 each. In the worst case, brute force costs order n times m.

Rabin-Karp

Rolling Hashes Over Each Window

Comparing two m-character strings costs m comparisons, but comparing two numbers costs one. Rabin-Karp turns every window of m characters into a number, a hash. Only when a window's hash equals the pattern's does it look at the characters. It's the polynomial hash from chapter 14, kept small with a prime modulus. A fresh hash for every window would cost m steps again. A rolling hash updates in constant time: drop the leading character, multiply by the base, add the new one. Run it on abracadabra, with the pattern cada, base 31, and modulus 101. The rolled hash equals a fresh one for every window. And only the window cada has the pattern's hash, 68.

Common Mistake

Negative Remainders and Math.floorMod

One trap. The subtraction can go negative, and Java's percent operator keeps the sign of its left side. Take the step from raca to acad. After dropping the r, the value is minus 10,980. Percent then gives minus 11, which can never equal a pattern hash, so a real match would be missed. Math.floorMod gives 90, the correct hash of acad.

False Alarms

Equal Hashes Need a Character Check

Equal hashes don't prove equal strings. Aa and BB share Java's hash code, 2112. So a matching hash can be a false alarm. So Rabin-Karp always confirms with the characters. Here, a hundred thousand random letters are searched for hello, with three different moduli. With modulus 101, there were 943 false alarms. Near ten thousand, just 7. Near a billion, none. With a large modulus, the expected cost is order n plus m. But the worst case is still n times m, when every window really is a match.

KMP Failure Function

Remembering What a Partial Match Taught

Brute force forgets what a partial match taught it. Say a b a b d has matched a b a b, then fails. The last four text characters are known. The next start can only be where a suffix of the matched part is also a prefix. Here that's a b, so the pattern slides ahead, without looking back. The failure function stores this for every prefix. Fail of i is the length of the longest proper prefix of the pattern up to i, that's also a suffix of it. For a b a b a c a, it's 0, 0, 1, 2, 3, 0, 1. At index four, a b a b a ends with a b a, which is also how it begins. So fail of four is three.

KMP Search

The Text Is Never Reread

The search keeps j, the number of pattern characters matched so far. The text position i only ever moves forward. On a mismatch, j drops to fail of j minus one, and the same text character is compared again. Nothing in the text is reread. On the fifteen-letter text, KMP made 19 comparisons against brute force's 27. On the worst case for brute force, it made 19,901, under 2n. Every comparison either moves i forward, or lowers j. So the total is at most 2n, plus order m to build the failure function, in every case. And because it reads the text once, left to right, KMP also works on a stream.

Quick Check

Failure Function for aabaa

Quick check. Build the failure function for the pattern a a b a a. For each prefix, find the longest proper prefix that's also a suffix. What array comes out? Pause and predict. Zero, one, zero, one, two. For a a, the border is a, so one. a a b has no border: zero. a a b a ends in a, which is also its start: one. And a a b a a ends with a a, which is also how it begins: two.

Horspool

Comparing From the Right and Jumping Ahead

Boyer-Moore asks a bolder question: can some text characters be skipped entirely? It compares from the right end of the pattern instead. If the text character under the window's last cell isn't in the pattern at all, no shift that overlaps it can work. So the pattern jumps clear past it. Horspool's version keeps just this bad-character idea. The shift table holds each character's distance from the end, ignoring the last cell. Others jump the full length. For EXAMPLE, E jumps six, X five, and so on, down to L, one. Any other character jumps seven. Run it on HERE IS A SIMPLE EXAMPLE. The first window ends in S, which isn't in the pattern, so one comparison buys a jump of seven. In all, 15 comparisons, for a text of 24 characters: fewer than its length.

Quick Check

A Horspool Jump After a Failed A

Quick check. The pattern is A B C A B. During a Horspool search, a window ends in the letter A, and the comparison fails. How far does the pattern jump? Pause and predict. One place. The shift values are filled left to right, so the A at index three overwrites the A at index zero. Its distance from the end is one. Four would use the first A, and the pattern could jump past a real match. Five is only for characters that aren't in the pattern.

Measurement

Four Methods on the Same Inputs

Now measure all four on the same inputs. Every method returned exactly the same positions as String.indexOf. On a million random letters, brute force and KMP each made about one comparison per character. Horspool's jumps cut that to about 15 percent. On the input built to hurt brute force, it made 99 million comparisons. KMP made under 200,000, and Rabin-Karp none, since no hash ever matched. When the pattern occurs at every position, every method but KMP pays 99 million. KMP stays at n: 100,000.

Decision Guide

Which Matcher for Which Job

So which one? For a short text, or a one-off search, brute force or indexOf is fast enough. For one pattern in a big text over a large alphabet, Horspool or Boyer-Moore skips most of it. When the worst case must be bounded, or the text is a stream, use KMP. Rabin-Karp shines for many patterns of the same length at once: one rolling hash serves them all, with their hashes in a set. And for words that share beginnings, a structure built for prefixes fits better: the trie, in lesson 16.10.

Key Takeaways

Four Pattern Matchers in Brief

To sum up. Brute force tries every shift, and costs n times m in the worst case. Rabin-Karp compares rolling hashes, confirms with the characters, and needs floorMod for negative values. KMP's failure function means the text is never reread: at most 2n comparisons. Horspool compares from the right, and jumps by the window's last character.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Pattern Matching: Finding a Word Inside a Text

What is the worst-case time of brute-force string matching?
Brute-force string matching costs order n times m comparisons in the worst case, for a text of n characters and a pattern of m. That happens when nearly every shift matches almost the whole pattern before failing. For example, searching 10,000 a's for 99 a's followed by a b takes 9,901 shifts of 100 comparisons each, or 990,100 comparisons. On typical text, most shifts fail at the first character.
How does the Rabin-Karp algorithm work?
Rabin-Karp turns each window of m text characters into a hash number and compares it with the pattern's hash, checking characters only when the hashes are equal. A rolling hash updates in constant time by dropping the leading character, multiplying by the base, and adding the new one, modulo a prime. Different strings can share a hash, so every hash match is confirmed character by character. In Java, Math.floorMod keeps the hash from going negative.
What is the KMP failure function?
The KMP failure function stores, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix of it. For the pattern ababaca, the values are 0, 0, 1, 2, 3, 0, 1. On a mismatch, KMP lowers its matched count to the failure value instead of moving back in the text, so the search makes at most 2n comparisons plus order m to build the table.
How does the Horspool algorithm skip characters?
Horspool compares the pattern from its right end and, after each attempt, shifts by an amount set by the text character under the window's last cell. Its shift table stores each pattern character's distance from the end, ignoring the last cell, and characters not in the pattern shift by the full pattern length. For EXAMPLE, E shifts six and any absent character shifts seven, so much of the text is skipped.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →