liveBook · Manning

Sliding window

As explained in Algorithms Every Programmer Should Know

The sliding window technique processes a contiguous portion of a sequence while shifting it incrementally across the sequence.

In Rabin–Karp string search, a sliding window keeps a contiguous text segment the same length as the pattern and shifts it one character at a time. Instead of recalculating each window’s hash, subtract the character leaving and add the one entering. When hashes match, compare the characters to rule out a collision. section 4.4 section 4.1

Updating the hash

For the window ALI, the simple hash is 22. Shift to LIC by removing A’s value (1) and adding C’s value (3): 22 − 1 + 3 = 24. The next window’s hash is updated without summing all its characters again. 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 the pattern-length window shift one character, with A leaving on the left as C enters on the right. section 4.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains the one-character hash update and collision check, and gives pseudocode and a Python implementation.
Examples
Traces the hash change from ALI to LIC and illustrates a pattern-length window shifting across text.
What you can do after
Apply the rolling update to move through text windows during Rabin–Karp search.
How it connects
Connects sliding windows to Rabin–Karp, rolling hash, string matching, and hash collisions.

Also explained in

Compare how 8 books explain sliding window →

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.