Lesson 21 · Core algorithms

String Hashing

Polynomial prefix hashes turn substring comparisons into O(1) arithmetic candidates, with collision management required whenever correctness must be exact.

Polynomial representation

Map characters to positive integers and define a polynomial hash with base B modulo prime M. Prefix hashes accumulate characters with powers, converting a substring into a difference of two prefixes after aligning exponents.

Mapping a character to zero can erase leading occurrences in some conventions. Base, modulus, mapping, and orientation must remain identical across every string being compared.

Characters become polynomial coefficients
Use one consistent orientation
Avoid ambiguous zero coefficients

Substring extraction

With H[i+1]=(H[i]·B+value[i]) mod M, hash(l,r)=H[r]−H[l]·B^(r−l) modulo M for half-open [l,r). Precompute powers through the maximum length.

Normalize subtraction into [0,M); language remainder rules differ for negative values. The formula is O(1), while preprocessing hashes and powers is O(N).

Use half-open substring boundaries
Precompute powers
Normalize modular subtraction

Key reference

Terms, operations, and practical uses

Polynomial hash

BaseBase is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
ModulusModulus is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Character mappingCharacter mapping is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Prefix extraction

Prefix hashPrefix hash is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Power tablePower table is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Substring hashSubstring hash is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Collision handling

Double hashingDouble hashing is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Exact verificationExact verification is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Randomized baseRandomized base is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Prefix hashes compare two substrings

s="banana";b=911382323;m=1000000007;n=len(s);h=[0]*(n+1);p=[1]*(n+1)
for i,ch in enumerate(s):h[i+1]=(h[i]*b+ord(ch))%m;p[i+1]=p[i]*b%m
def sub(l,r):return (h[r]-h[l]*p[r-l])%m
print("Equal substrings:",sub(1,4)==sub(3,6))

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
    string s="banana";
    long long b=911382323,m=1000000007;
    vector<long long> h(7),p(7,1);
    for(int i=0;i<6;i++) h[i+1]=(h[i]*b+s[i])%m,p[i+1]=p[i]*b%m;
    auto sub=[&](int l,int r) {
        return (h[r]-h[l]*p[r-l]%m+m)%m;
    };
    cout << "Equal substrings: " << (sub(1,4)==sub(3,6)?"True":"False") << '\n';
}

class Main {
    public static void main(String[] args) {
        String s="banana";
        long b=911382323L,m=1000000007L;
        long[] h=new long[7],p=new long[7];
        p[0]=1;
        for(int i=0;i<6;i++) {
            h[i+1]=(h[i]*b+s.charAt(i))%m;
            p[i+1]=p[i]*b%m;
        }
        long x=(h[4]-h[1]*p[3]%m+m)%m,y=(h[6]-h[3]*p[3]%m+m)%m;
        System.out.println("Equal substrings: "+(x==y?"True":"False"));
    }
}

Watch it run

Step through it

Running on banana: compare ana at 1 and 3

Output

Collisions and correctness

A finite hash maps many strings to one value, so collisions are unavoidable. Hash inequality proves strings differ; equality only creates a candidate. Exact applications verify characters or use a deterministic algorithm.

Two independent large moduli make accidental collision extremely unlikely but not impossible. Randomizing a valid base can resist adversarial inputs; cryptographic guarantees require a different construction.

Inequality is definitive
Equality is probabilistic
Adversarial inputs change the risk model

Applications

Prefix hashes enable repeated substring equality, palindrome checks using a reversed string, binary search for longest common prefix, duplicate-substring detection, and Rabin–Karp windows. They are most valuable when many related queries amortize preprocessing.

When edits occur, static prefixes no longer apply directly; Fenwick or segment trees can maintain weighted coefficients. Suffix arrays or deterministic string algorithms may be preferable when collision-free ordering is required.

Preprocessing serves many queries
Reverse hashes test palindromes
Dynamic strings need indexed structures

Engineering tests

Test empty substrings, length one, whole strings, repeated characters, different lengths, negative subtraction, and deliberately tiny moduli that force collisions. Never compare hashes for unequal lengths as though equality implied equal strings.

Use a multiplication type wide enough for B·H before reduction, or safe modular multiplication. State whether output indexes refer to bytes or code points.

Length is part of equality
Wide intermediates prevent overflow
Collision tests verify fallback behavior

Comparing hashes across strings

To compare substrings from different strings, build prefixes with the same base, modulus, character mapping, and power convention. Lengths must match before equality is meaningful. Concatenating hashes also requires multiplying the left hash by the correct power of the right length.

Store both moduli in one value object so callers cannot accidentally compare only one component. When a hash selects a candidate for an irreversible decision, perform exact verification. Randomized bases should exclude zero, one, and values too close to the modulus that create weak patterns.

Prefix hashes remain immutable snapshots: mutating the underlying string invalidates every later prefix. Version or rebuild them rather than returning stale comparisons. For security-sensitive authentication or untrusted collision resistance, use a cryptographic construction rather than a competitive-programming polynomial hash.

The subtraction formula follows from the prefix polynomial: H[r] contains H[l] shifted by exactly r−l powers plus the desired suffix contribution. Multiplying H[l] by that power aligns the unwanted prefix before subtraction. Different conventions place powers in the opposite direction, so formulas cannot be copied across implementations without deriving the alignment. Test empty substrings if the API permits them, full-string extraction, equal content at different positions, unequal lengths, negative intermediate subtraction, and deliberately tiny moduli that create collisions. The tiny-modulus test verifies that exact comparison is actually performed where correctness requires it. Keep index intervals half-open so substring length is always r−l.

Share every hash parameter
Length participates in the hash contract
Verify before irreversible decisions