Rolling hash

Why this matters

Many programs compare pieces of a long text again and again. A plagiarism checker compares passages from two essays. A tool that studies DNA looks for stretches of letters that repeat. An editor checks whether two blocks of text are the same before it merges them.

Comparing two substrings letter by letter costs one step per letter. A substring of 1,000 letters costs 1,000 steps for one comparison. If you compare a million pairs of such substrings, the total is a billion steps.

A rolling hash avoids most of that work. A hash is a number computed from a piece of data. The rolling hash gives every substring of a text a number, so that two equal substrings always get equal numbers. After one pass over the text, the number for any substring can be read in a fixed number of steps. The length of the substring does not change that cost. Cost that does not depend on the input size is called constant time.

There is one catch. Two different substrings can, rarely, get the same number. This is called a collision. So a matching number is a strong hint, not a proof. The second check in this lesson compares the actual characters whenever the numbers match. That check is what makes the answers correct.

The naive substring search in lesson 07 compared letters one at a time. This lesson replaces most of those letter comparisons with number comparisons. The name "rolling" comes from a window that slides along the text. The method here is close to the Rabin-Karp search, a well-known algorithm that uses this idea.

A hash is a number built from letters

A computer stores each character as a number. The number is the character's code. In the ASCII table, which most systems use for the basic letters, 'a' is 97, 'b' is 98, and 'c' is 99.

To turn a string into one number, start with 0. For each letter from left to right, multiply the number so far by a fixed base, then add the letter's code. The base is a number you choose. This is the same way you read decimal digits: "12" means 1 times 10 plus 2.

Here is the process for "ab" with base 10, which is easy to follow by hand:

• Start with 0.
• Read a, code 97. The number becomes 0 times 10 plus 97, which is 97.
• Read b, code 98. The number becomes 97 times 10 plus 98, which is 1068.

So the hash of "ab" is 1068 in this toy version. The base matters because it gives position a weight. The string "ba" gives 98 times 10 plus 97, which is 1077. Different order, different number.

Real hashes use a larger base, such as 131, and a modulus. The modulus is a fixed number, and every result is replaced by its remainder after division by the modulus. This keeps the numbers small. The remainder of x divided by M is written x mod M. For example, 1068 mod 1000 is 68.

The modulus used here is 1000000007, a prime number. The calculations need one more rule. Every intermediate result must stay under about 4 billion, so that a product of two results fits in a 64-bit unsigned integer. With a modulus near one billion, a product is near one quintillion, and a 64-bit unsigned integer holds up to about 18 quintillion. The type uint64_t from <cstdint> is 64 bits.

Prefix hashes: one pass over the text

A prefix of a string is its first few letters. The prefix hash at position i is the hash of the first i letters. Call these values prefix[0], prefix[1], and so on, up to prefix[n], where n is the length of the string.

• prefix[0] is the hash of the empty string, which is 0.
• Each next value comes from the one before it: prefix[i + 1] equals prefix[i] times the base, plus the code of letter i, then reduced by the modulus.

Building all of them takes one loop over the string, so the setup costs time proportional to n. This is the linear setup from the lesson summary.

The method also needs power[k], which is the base multiplied by itself k times, reduced by the modulus. power[0] is 1. Each value comes from the one before it, so this is built in the same loop.

Reading one substring

Now the key step. Suppose you want the hash of the substring that starts at start and has length len. Its letters are the ones at positions start through start + len - 1.

The prefix prefix[start + len] holds the hash of everything up to the end of that substring. It includes two parts: the letters before the substring, and the substring itself. Each letter before the substring has been multiplied by the base once for every letter after it. So the letters before the substring are stored as prefix[start] times base to the power len.

That gives one formula:

hash of substring = prefix[start + len] minus prefix[start] times base to the power len

Everything is done mod the modulus. Take the earlier "ab" example with base 10, with no modulus for simplicity. prefix[2] is 1068 and prefix[1] is 97. The substring "b" starts at 1 and has length 1. So:

• prefix[2] is 1068.
• prefix[1] times 10 to the power 1 is 970.
• 1068 minus 970 is 98.

The code for 'b' is 98, so the formula gives the right answer. The same thing works for any substring, and the cost is one multiplication, one subtraction, and one remainder. That cost does not depend on the length of the substring.

Compare the two ways of checking two substrings of length L:

The second row is cheaper when many comparisons are made. If you make only one comparison, the setup costs about as much as the direct check.

The PrefixHash class

The code below stores the prefix and power tables for one string. Save it as a file named ph.hpp. Each example in this lesson starts with #include "ph.hpp". Put the example and ph.hpp in the same folder and compile with g++ -std=c++17 -Wall example.cpp -o example.

#pragma once
#include <cstdint>
#include <string>
#include <vector>
 
// Prefix hashes for one string, using a fixed modulus and base.
class PrefixHash {
public:
    PrefixHash(const std::string& s, uint64_t mod, uint64_t base)
        : mod_(mod), base_(base), prefix_(s.size() + 1, 0), power_(s.size() + 1, 1) {
        for (std::size_t i = 0; i < s.size(); i++) {
            uint64_t code = static_cast<unsigned char>(s[i]);
            prefix_[i + 1] = (prefix_[i] * base_ + code) % mod_;
            power_[i + 1] = (power_[i] * base_) % mod_;
        }
    }
 
    // Hash of the substring that starts at index start and has length len.
    uint64_t get(std::size_t start, std::size_t len) const {
        uint64_t upper = prefix_.at(start + len);
        uint64_t removed = prefix_.at(start) * power_.at(len) % mod_;
        return (upper + mod_ - removed) % mod_;
    }
 
private:
    uint64_t mod_;
    uint64_t base_;
    std::vector<uint64_t> prefix_;
    std::vector<uint64_t> power_;
};

Three details in this code matter.

The cast static_cast<unsigned char> keeps each code between 0 and 255. The type char can be negative on some systems, and a negative code would break the arithmetic.

In get, the line upper + mod_ - removed adds the modulus before the subtraction. The reason is explained in the mistakes section.

The .at() calls check the index. If an index is out of range, the program throws an error instead of reading memory it does not own. The mistakes section shows the message.

Example 1: comparing two substrings

The first example checks whether two substrings of "banana" are equal. Each check uses only the numbers.

#include <cstdint>
#include <iostream>
#include <string>
#include "ph.hpp"
 
constexpr uint64_t MOD1 = 1000000007ULL;
constexpr uint64_t BASE1 = 131ULL;
 
int main() {
    std::string text = "banana";
    PrefixHash h(text, MOD1, BASE1);
    std::cout << "hash of ana at 1: " << h.get(1, 3) << "\n";
    std::cout << "hash of ana at 3: " << h.get(3, 3) << "\n";
    std::cout << "hash of ban at 0: " << h.get(0, 3) << "\n";
    std::cout << "ana at 1 equals ana at 3: " << (h.get(1, 3) == h.get(3, 3)) << "\n";
    std::cout << "ban at 0 equals ana at 1: " << (h.get(0, 3) == h.get(1, 3)) << "\n";
    std::cout << "hash of ab: " << PrefixHash("ab", MOD1, BASE1).get(0, 2) << "\n";
    std::cout << "hash of b: " << PrefixHash("ab", MOD1, BASE1).get(1, 1) << "\n";
    return 0;
}

Output from g++ 15.2 on Linux:

hash of ana at 1: 1679124
hash of ana at 3: 1679124
hash of ban at 0: 1694595
ana at 1 equals ana at 3: 1
ban at 0 equals ana at 1: 0
hash of ab: 12805
hash of b: 98

The two copies of "ana" have the same number, so the check says equal. The number for "ban" is different, so that check says not equal.

The last two lines match the arithmetic by hand. The hash of "ab" is 97 times 131 plus 98, which is 12805. The hash of "b" is 98. The exact values for "ana" depend on the base and modulus, so do not try to match them by hand. Check the equality instead.

Note that this example only compares numbers. It is not a complete check. If the numbers were equal by collision, the answer would be wrong. The next two examples add the second check.

Example 2: finding every occurrence of a pattern

The naive search from lesson 07 tried every starting position and compared letters. This version does the same loop over starting positions, but each window is checked by its number. The window's number comes from get, so each check costs a fixed number of steps.

The function compares characters only when the numbers match. That is the second check.

#include <cstddef>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include "ph.hpp"
 
constexpr uint64_t MOD1 = 1000000007ULL;
constexpr uint64_t BASE1 = 131ULL;
 
// Returns every index where pattern starts inside text.
std::vector<std::size_t> findAll(const std::string& text, const std::string& pattern) {
    std::vector<std::size_t> hits;
    std::size_t m = pattern.size();
    if (m == 0 || m > text.size()) {
        return hits;
    }
    PrefixHash textHash(text, MOD1, BASE1);
    PrefixHash patternHash(pattern, MOD1, BASE1);
    uint64_t target = patternHash.get(0, m);
    for (std::size_t start = 0; start + m <= text.size(); start++) {
        // The hash check is fast. The string compare confirms a real match.
        if (textHash.get(start, m) == target && text.compare(start, m, pattern) == 0) {
            hits.push_back(start);
        }
    }
    return hits;
}
 
int main() {
    std::string text = "abracadabra";
    for (std::string pattern : {"abra", "ra", "xyz", "a"}) {
        std::cout << pattern << ":";
        for (std::size_t i : findAll(text, pattern)) {
            std::cout << " " << i;
        }
        std::cout << "\n";
    }
    std::cout << "aa in aaaa:";
    for (std::size_t i : findAll("aaaa", "aa")) {
        std::cout << " " << i;
    }
    std::cout << "\n";
    return 0;
}

Output:

abra: 0 7
ra: 2 9
xyz:
a: 0 3 5 7 10
aa in aaaa: 0 1 2

Walk through the first line. "abra" appears at positions 0 and 7 of "abracadabra". The loop tries every start from 0 to 7, which is n - m for n = 11 and m = 4. At each start, get gives the number of the window, and it is compared with the number of the pattern. The windows at 0 and 7 have the same number as the pattern, and the character check confirms both.

The overlapping case "aa" in "aaaa" returns 0, 1, and 2. The windows may overlap, and the search counts each one.

The cost is one pass over the text for the setup, then a fixed number of steps for each window. The character compare runs only for windows whose number matches. For most windows it never runs, so the search is fast on ordinary text.

Example 3: the longest repeated substring

The third example is harder. It finds the longest substring that appears at two different starting positions in the same text. The copies may overlap. In "banana", the answer is "ana", which appears at positions 1 and 3.

Two ideas make this work.

The first is a rule about lengths. If some substring of length L appears twice, then some substring of length L - 1 also appears twice. Remove the last letter from both copies, and the shorter copies still match. So the answer to "does a repeat of length L exist?" gets "yes" for every length up to the best answer and "no" for every length above it. A rule like this lets a binary search find the boundary. A binary search keeps halving the range of possible answers.

The second idea is to use two hashes with two different moduli and bases. A single hash can collide, and the chance grows as the number of pairs grows. With two hashes packed into one key, a key match happens only when both hashes match. The character check still runs on every key match, so the answer is correct either way.

#include <cstddef>
#include <cstdint>
#include <iostream>
#include <optional>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#include "ph.hpp"
 
constexpr uint64_t MOD1 = 1000000007ULL;
constexpr uint64_t MOD2 = 998244353ULL;
constexpr uint64_t BASE1 = 131ULL;
constexpr uint64_t BASE2 = 137ULL;
 
// Looks for two different starts of a window of length len that hold the same text.
std::optional<std::pair<std::size_t, std::size_t>> findRepeat(const std::string& text, std::size_t len,
                                                              const PrefixHash& h1, const PrefixHash& h2) {
    std::unordered_map<uint64_t, std::vector<std::size_t>> seen;
    for (std::size_t start = 0; start + len <= text.size(); start++) {
        // Pack both hashes into one key. h2 is below MOD2, so each pair gives its own key.
        uint64_t key = h1.get(start, len) * MOD2 + h2.get(start, len);
        std::vector<std::size_t>& earlier = seen[key];
        for (std::size_t first : earlier) {
            // Equal hashes are not proof. Compare the characters before reporting a repeat.
            if (text.compare(first, len, text, start, len) == 0) {
                return std::make_pair(first, start);
            }
        }
        earlier.push_back(start);
    }
    return std::nullopt;
}
 
// Returns the longest substring that appears at two different starts. The copies may overlap.
std::string longestRepeated(const std::string& text) {
    if (text.size() < 2) {
        return "";
    }
    PrefixHash h1(text, MOD1, BASE1);
    PrefixHash h2(text, MOD2, BASE2);
    std::string best;
    std::size_t lo = 1;
    std::size_t hi = text.size() - 1;
    while (lo <= hi) {
        std::size_t mid = lo + (hi - lo) / 2;
        auto found = findRepeat(text, mid, h1, h2);
        if (found) {
            best = text.substr(found->first, mid);
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return best;
}
 
int main() {
    for (std::string text : {"banana", "abracadabra", "aaaa", "xyz", "a"}) {
        std::cout << text << " -> \"" << longestRepeated(text) << "\"\n";
    }
    return 0;
}

Output:

banana -> "ana"
abracadabra -> "abra"
aaaa -> "aaa"
xyz -> ""
a -> ""

The binary search tests a length, mid, at each step. If findRepeat finds a repeat, the answer is at least mid, so the search moves up. If not, the answer is below mid, so the search moves down. For "banana", the search tests length 3 first, then length 4. Length 3 repeats, so the search moves up. Length 4 does not repeat, so the best answer is "ana".

findRepeat keeps a list of earlier starts for each key. When a new window has a key already in the table, the function compares the characters with each earlier start that has that key. A real repeat returns at once. A collision, where the keys match but the characters differ, does not return, and the search continues.

The cost is roughly n steps for each length tested, and about log n lengths are tested. The total is about n log n steps on average. Each key lookup is a fixed cost, and a character compare runs only when two keys match, so this is fast for texts of thousands of letters.

Common mistakes

Trusting a hash match

A matching number is not proof. Small moduli make collisions easy to see. The program below uses the modulus 11 and the base 10. Each two-letter string gets a number, and the program looks for two strings with the same number:

#include <cstdint>
#include <iostream>
#include <map>
#include <string>
#include "ph.hpp"
 
int main() {
    std::map<uint64_t, std::string> firstWithHash;
    for (char a = 'a'; a <= 'z'; a++) {
        for (char b = 'a'; b <= 'z'; b++) {
            std::string s{a, b};
            uint64_t h = PrefixHash(s, 11, 10).get(0, 2);
            if (firstWithHash.count(h)) {
                std::cout << "collision: \"" << firstWithHash[h] << "\" and \"" << s
                          << "\" both hash to " << h << "\n";
                return 0;
            }
            firstWithHash[h] = s;
        }
    }
    return 0;
}

Output:

collision: "aa" and "al" both hash to 0

The strings "aa" and "al" are different, and they have the same number. A program that trusts the number would say they are equal. The character check in findAll and findRepeat catches this. With the large modulus used in the examples, collisions are rare, but they are still possible.

Subtracting before adding the modulus

Unsigned integers cannot go below zero. When a subtraction would go below zero, the result wraps around to a very large number. The remainder of that large number is not the correct remainder.

#include <cstdint>
#include <iostream>
 
int main() {
    uint64_t upper = 5;
    uint64_t removed = 9;
    uint64_t mod = 7;
    std::cout << "wrapped: " << (upper - removed) % mod << "\n";
    std::cout << "correct: " << (upper + mod - removed) % mod << "\n";
    return 0;
}

Output:

wrapped: 5
correct: 3

The correct remainder of 5 - 9 is 3, because -4 mod 7 is 3. The wrapped version gives 5. No error is shown, so this bug is silent. Adding the modulus before subtracting keeps the value positive. The get function in the PrefixHash class does this.

Reading past the end of the text

A call such as get(4, 5) on a 6-letter string asks for positions 4 to 8. The .at() calls in get catch this:

#include <cstdint>
#include <iostream>
#include <stdexcept>
#include "ph.hpp"
 
int main() {
    try {
        PrefixHash h("abcdef", 1000000007ULL, 131ULL);
        std::cout << h.get(4, 5) << "\n";
    } catch (const std::out_of_range& e) {
        std::cout << "error: " << e.what() << "\n";
    }
    return 0;
}

Output:

error: vector::_M_range_check: __n (which is 9) >= this->size() (which is 7)

The message says that index 9 was asked for, and the vector has 7 entries. The numbers mean start + len was 9, while the prefix array only has 7 entries for a 6-letter string. Check that start + len is at most the string length before calling get.

Forgetting an include

Using std::optional needs #include <optional>. Without it, the compiler reports an error at the first use:

missing_optional.cpp:4:6: error: ‘optional’ in namespace ‘std’ does not name a template type
    4 | std::optional<int> firstDigit(const std::string& s) {
      |      ^~~~~~~~
missing_optional.cpp:2:1: note: ‘std::optional’ is defined in header ‘<optional>’; this is probably fixable by adding ‘#include <optional>’

The compiler also reports a second error, 'firstDigit' was not declared in this scope, because the first error stopped the declaration. Fix the first error, and the second one goes away.

Using a 32-bit type for the numbers

If the numbers are stored in int, a product of two values near one billion does not fit in 32 bits. Signed overflow in C++ is undefined behaviour, so the program may give wrong answers with no error. The option -Wall does not always warn about this. Store the values in uint64_t, as the PrefixHash class does.

Using one fixed base on untrusted input

A fixed base and modulus are fine for practice and for data you trust. If someone can choose the input, they can build strings that collide with your fixed numbers. For that case, pick the base at random when the program starts. The collision check in the examples still applies in either case.

Practice

Exercise 1: compute by hand

Using the base 131 and the modulus 1000000007, find the hash of "ab" and the hash of "b" by the formula. Check your answer by running the program in Example 1.

Show the answer

The hash of "ab" is 97 times 131 plus 98, which is 12805. For "b", the formula is prefix[2] minus prefix[1] times 131. prefix[1] is 97 and prefix[2] is 12805, so the result is 12805 minus 12707, which is 98. Both match the program output.

Exercise 2: compare two substrings

Write a function bool sameSubstring(const std::string& s, std::size_t a, std::size_t b, std::size_t len) that returns true when the substrings of length len starting at a and at b are equal. Use the hash for speed and a character check to confirm. Return false when either substring goes past the end of s.

Show the answer

bool sameSubstring(const std::string& s, std::size_t a, std::size_t b, std::size_t len) {
    if (a + len > s.size() || b + len > s.size()) {
        return false;
    }
    PrefixHash h(s, MOD1, BASE1);
    return h.get(a, len) == h.get(b, len) && s.compare(a, len, s, b, len) == 0;
}

Running this on "banana" gives true for (1, 3, 3), false for (0, 1, 3), and false for (2, 4, 5), because the last one goes past the end of the string.

Exercise 3: check for a rotation

A rotation of a string moves some letters from the front to the back. "cdab" is a rotation of "abcd". Write bool isRotation(const std::string& a, const std::string& b) that returns true when b is a rotation of a. Use findAll from Example 2.

Show the answer

Put a next to itself, so "abcd" becomes "abcdabcd". Every rotation of a appears in that doubled string. So b is a rotation of a when the lengths are equal and b appears in the doubled string.

bool isRotation(const std::string& a, const std::string& b) {
    return a.size() == b.size() && !findAll(a + a, b).empty();
}

Running this gives true for ("abcd", "cdab"), false for ("abcd", "acbd"), and false for ("abc", "abcd"), because the lengths differ.

Exercise 4: the empty string and a NUL character

A NUL character is a character with code 0. Show that the empty string and a string holding one NUL character have the same hash. Explain why this is not a problem for the search functions in this lesson.

Show the answer

The hash of the empty string is 0, because the loop never runs. The string with one NUL character has the hash 0 * 131 + 0, which is also 0. The two strings collide. The search functions compare the characters after a match, so the two strings are never reported as equal. A collision costs one extra character check, not a wrong answer.

The program that prints these values gives empty: 0 and nul: 0.

Exercise 5: count the steps

A text has 10,000 letters. You want to compare 1,000 pairs of substrings, each of length 500. Estimate the number of steps for letter by letter comparison, and for the rolling hash method with its setup. Assume the pairs are not equal, so no character check runs for them.

Show the answer

Letter by letter, each pair can take up to 500 steps, so 1,000 pairs take up to 500,000 steps. Rolling hash takes 10,000 steps for the setup. Then each pair costs a fixed small number of steps, so 1,000 pairs cost a few thousand more steps. The total is about 13,000 steps, which is far below 500,000. If the pairs were equal, each one would also need up to 500 character steps for the check, so the saving would be smaller.

Summary

• A rolling hash gives each substring a number that can be read in a fixed number of steps.
• Prefix hashes take one pass over the text, and the formula prefix[start + len] minus prefix[start] times the base to the power len gives any substring's number.
• Equal substrings always have equal numbers, but different substrings can collide.
• Compare the characters whenever the numbers match, so a collision cannot give a wrong answer.
• Use uint64_t, keep every intermediate result below the modulus, and add the modulus before a subtraction.