liveBook · Manning

Substring

As explained in Algorithms Every Programmer Should Know

A substring is a contiguous non-empty sequence of characters within a string.

A substring is a non-empty, contiguous sequence of characters within a string. In Rabin–Karp string searching, each text window the size of the pattern is treated as a candidate substring: matching hashes prompt a character-by-character check. section 4.1

A window that moves

When a window moves one character to the right, its leftmost character leaves and a new character enters. The resulting window is another candidate substring; if its hash matches the pattern’s, compare the characters to rule out a collision. section 4.1

Figure 4.3 A sliding window of size equal to the size of the pattern. The window slides by one character. The character A exits from the left, and the character C enters.

See how a fixed-size window shifts by one character, replacing the character that leaves with the one that enters. section 4.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines substrings and explains their role in hash-based window comparison, including character checks for collisions.
Examples
Uses text windows such as ALI and LIC to illustrate hash comparison and one-character window shifts.
What you can do after
Apply Rabin–Karp by comparing candidate-window hashes and checking matching windows character by character.
How it connects
Connects substrings to strings, string matching, Rabin–Karp, rolling hashes, and hash collisions.

Also explained in

Compare how 6 books explain substring →

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.