liveBook · Manning

Pattern

As explained in Algorithms Every Programmer Should Know

A pattern is a character sequence whose occurrence is sought within a text during string matching.

A pattern is the character sequence you want to find in a text. String matching checks whether that sequence occurs and where. section 4.1

Searching for COOL

In ALICEANDJOEBAKEDCOOKIES, searching for COOL means checking candidate positions in the text. A simple character-by-character search can match three letters before finding that the last one differs. section 4.1

Figure 4.1 The pattern COOL is to be matched with the text “ALICEANDJOEBAKEDCOOKIES”. Each character is checked one by one. The first box shows that A and C are compared. With no successful match, we move the pattern forward by one character and continue comparing. The second box shows three characters matched, and the last character doesn’t, concluding the pattern is not in the text only after checking the first three characters.

Follow the pattern across the text to see how a mismatch can occur after several matching characters. section 4.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through character-by-character matching before turning to hashes; does not develop the pattern concept independently.
Examples
Uses COOL and JOE as patterns searched for in text.
What it assumes
Starts from basic character comparisons before introducing numeric hashes.
What you can do after
Understand how a target sequence is checked against candidate positions in a text.
How it connects
Connects patterns to string matching, Rabin–Karp, hashing, and sliding windows.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.