AlgoViz
HomeStrings

Hashing In Strings

Easy

Polynomial hashing for O(1) substring compare

Problem

Learn polynomial string hashing to compare substrings in O(1) after O(n) precomputation.

In simple words

Turn a string into a number so substrings can be compared instantly.

The idea

Treat a string as a number in some base modulo a large prime, and precompute prefix hashes so any substring's hash is a subtraction and a multiplication away. Comparing two substrings then costs O(1) instead of O(length).

The trick

  • hash(l..r) = pre[r+1] - pre[l] * base^(r-l+1), all modulo the prime.
  • Precompute the powers of the base alongside the prefixes.
  • Two different moduli make an accidental collision effectively impossible.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — hash of 'abc' Values: 0.

1/2
Optimal
timeO(n) buildspaceO(n)
1h[i+1] = h[i]*p + s[i]2substring hash = h[r+1] - h[l]*p^(r-l+1)

Input

array
[0]

Output

answer
—

Check yourself

1 quick question about this walkthrough. A wrong answer costs nothing.

Example

Input:
hash of 'abc'
Output:
a*p^2+b*p+c

Finished the walkthrough? Add it to your streak.