Skip to content
CCC Python Course

Hashing: polynomial rolling hash

Stage
5
Module
M5.4
Lessons
1

In this module

  • Implement polynomial rolling hash with (h * B + c) % M.
  • Remove the leading character using precomputed powers.
  • Detect hash collisions and use double hashing or a large modulus.
  • Use rolling hashes to count distinct substrings.

Before this module

M5.3Sliding windows with countsM4.1Hash-based lookupM4.6Number theory I

Lessons

  1. 1Polynomial rolling hash

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2020 S3
    Searching for Strings (opens on DMOJ in a new tab) DMOJ

    Find distinct permutations of a pattern in a text using rolling hashes.