SyntaxPilot
Courses/DSA and Coding Problems/Lesson 81
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 81 of 90

Rabin-Karp and the Z-algorithm

queued

These are the notes for DSA episode 81. You export four years of your class group chat into one file and want every place a word appears. We try the obvious way, letter by letter at every start (correct, then Time Limit Exceeded on two million letters), see that neighbouring windows re-read the same letters, and give every window a fingerprint. A plain sum collides ("listen" is found inside "silent"), so we read the window as a number in base 131, modulo 1,000,000,007: the rolling hash of Rabin-Karp. It is fast until a pattern matches a million times and every hit must be verified, so we build the Z-array with its box and get O(n + m) guaranteed. Then three real bugs: Java's % keeping the minus sign, int overflow, and a missing $ separator. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The group chat In code
The exported chat file the text t, length n
The word you search for the pattern p, length m
One place the word could start a window t[i .. i + m)
"Found at message 3, 2,047, ..." the list of start indices
A short code that stands for a whole word a hash (fingerprint)

Every word, from zero

  • String matching: finding every position where a pattern occurs inside a text.
  • Text / pattern: the long string we search in (t, length n) and the short one we search for (p, length m).
  • Window: the m letters of the text starting at index i, the candidate place for a match.
  • Overlapping matches: matches that share letters, like "aa" at 0 and 1 in "aaaaa".
  • Character code: every char is a number in Java: 'a' = 97, 'b' = 98, '$' = 36.
  • Fingerprint / hash: one number computed from a window; equal strings always give equal hashes.
  • Collision: two different strings with the same hash, like "listen" and "silent" under a sum.
  • Anagram: the same letters in a different order.
  • Base: how much each place is worth compared with the next. In base 10, 31 is 3 × 10 + 1.
  • Rolling hash: a hash you can update in O(1) when the window slides one step: remove the old letter, shift, add the new one.
  • Modulo (%): the remainder after division. We keep hashes as remainders mod a large prime M so they stay small.
  • Prime: a number with no divisors except 1 and itself. 1,000,000,007 is a common choice.
  • Place value: what one letter adds to the hash because of its position: B^(m−1) for the first letter of a window.
  • Verify: compare the actual letters after the hashes match, to rule out a collision.
  • Rabin-Karp: string matching with a rolling hash plus verification (Richard Karp and Michael Rabin, 1987).
  • Z-array: z[i] = length of the longest stretch starting at i that matches the start of the string.
  • Separator: a character (here $) that appears in neither string, put between pattern and text.
  • Z-box [l, r): the earlier match that reaches furthest right; inside it the string copies its own beginning.
  • Overflow: an int result past 2³¹ − 1 (about 2.1 billion) wraps around to a wrong, often negative, number.
  • Linear time: O(n + m): the work grows in proportion to the input's length.

Problem statement

Given a text t and a pattern p, return the list of every index i such that t.substring(i, i + m) equals p, in increasing order. n can be a few million.

Text Pattern Answer Why
"abracadabra" "abra" [0, 7] two separate matches
"namaste india, namaste world" "namaste" [0, 15] a longer pattern (its hash wraps mod M)
"aaaaa" "aa" [0, 1, 2, 3] matches overlap
"chai" "chai" [0] pattern = whole text
"abc" "abcd" [] pattern longer than the text

Obvious idea: letter by letter

At every start i, compare the pattern letter by letter and stop at the first mismatch.

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        for (int i = 0; i + m <= n; i++) {
            int k = 0;
            while (k < m && t.charAt(i + k) == p.charAt(k)) k++;
            if (k == m) res.add(i);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("abracadabra", "abra"));
        System.out.println(find("namaste india, namaste world", "namaste"));
        System.out.println(find("aaaaa", "aa"));
        System.out.println(find("chai", "chai"));
        System.out.println(find("abc", "abcd"));
    }
}
[0, 7]
[0, 15]
[0, 1, 2, 3]
[0]
[]

All correct. Now the big test: the text is two million as, the pattern is a million as followed by one b.

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        for (int i = 0; i + m <= n; i++) {
            int k = 0;
            while (k < m && t.charAt(i + k) == p.charAt(k)) k++;
            if (k == m) res.add(i);
        }
        return res;
    }
    public static void main(String[] args) {
        String t = "a".repeat(2000000), a = "a".repeat(1000000);
        for (String p : new String[]{a + "b"}) {
            long t0 = System.nanoTime();
            int c = find(t, p).size();
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(c + " matches, " + ms + " ms");
        }
    }
}
Time limit exceeded

Why is it slow?

  • At each of about n − m + 1 starts we compare up to m letters: O(n × m).
  • Here every start matches a million letters and fails only on the b: about a million × a million = 10¹² comparisons.
  • Neighbouring windows share m − 1 letters, and we read them again every time.
  • Idea: give each window one number (a fingerprint) that we can update in O(1) when the window slides, and compare numbers instead of words.

Fingerprint idea 1: add up the letters

Slide by subtracting the letter that leaves and adding the letter that enters.

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return res;
        int hp = 0, ht = 0;
        for (int k = 0; k < m; k++) {
            hp += p.charAt(k);
            ht += t.charAt(k);
        }
        for (int i = 0; ; i++) {
            if (ht == hp) res.add(i);
            if (i + m == n) break;
            ht = ht - t.charAt(i) + t.charAt(i + m);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("abracadabra", "abra"));
        System.out.println(find("listen silent", "listen"));
    }
}
[0, 7]
[0, 7]

"listen" is reported at index 7, where the text says "silent". A sum ignores order, so anagrams collide.

The key insight: read the window as a number

With digits 3 1 4 1 5 9 and pattern "15", every window is a two-digit number, and sliding is O(1):

Window Computation Value Match?
3 1 first window 31 no
1 4 (31 − 3 × 10) × 10 + 4 14 no
4 1 (14 − 1 × 10) × 10 + 1 41 no
1 5 (41 − 4 × 10) × 10 + 5 15 yes, index 3
5 9 (15 − 1 × 10) × 10 + 9 59 no

For letters:

  • Each letter is a digit in base B = 131 (bigger than every character code we use).
  • The numbers get huge, so keep them mod M = 1,000,000,007.
  • Remove the old letter: ht = ht − t[i] × B^(m−1); then shift and add: ht = ht × B + t[i + m] (all mod M).
  • Two different windows can still share a remainder, so on a hash match we verify the letters.

Solution 1 in Java: Rabin-Karp

import java.util.*;

public class Main {
    static final long M = 1_000_000_007L, B = 131;
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return res;
        long hp = 0, ht = 0, pw = 1;
        for (int k = 0; k < m; k++) {
            hp = (hp * B + p.charAt(k)) % M;
            ht = (ht * B + t.charAt(k)) % M;
            if (k > 0) pw = pw * B % M;
        }
        for (int i = 0; ; i++) {
            if (ht == hp && t.startsWith(p, i)) res.add(i);
            if (i + m == n) break;
            ht = (ht - t.charAt(i) * pw % M + M) % M;
            ht = (ht * B + t.charAt(i + m)) % M;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("abracadabra", "abra"));
        System.out.println(find("namaste india, namaste world", "namaste"));
        System.out.println(find("aaaaa", "aa"));
        System.out.println(find("chai", "chai"));
        System.out.println(find("abc", "abcd"));
    }
}
[0, 7]
[0, 15]
[0, 1, 2, 3]
[0]
[]

The big test that timed out, then a pattern that matches everywhere:

import java.util.*;

public class Main {
    static final long M = 1_000_000_007L, B = 131;
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return res;
        long hp = 0, ht = 0, pw = 1;
        for (int k = 0; k < m; k++) {
            hp = (hp * B + p.charAt(k)) % M;
            ht = (ht * B + t.charAt(k)) % M;
            if (k > 0) pw = pw * B % M;
        }
        for (int i = 0; ; i++) {
            if (ht == hp && t.startsWith(p, i)) res.add(i);
            if (i + m == n) break;
            ht = (ht - t.charAt(i) * pw % M + M) % M;
            ht = (ht * B + t.charAt(i + m)) % M;
        }
        return res;
    }
    public static void main(String[] args) {
        String t = "a".repeat(2000000), a = "a".repeat(1000000);
        for (String p : new String[]{a + "b", a}) {
            long t0 = System.nanoTime();
            int c = find(t, p).size();
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(c + " matches, " + ms + " ms");
        }
    }
}
0 matches, 30 ms
Time limit exceeded

The first pattern never matches a hash, so no letter is ever compared. The second matches at 1,000,001 places and each match is verified with up to a million letter comparisons: 10¹² again. Rabin-Karp is O(n + m) plus m per hash match.

The Z-array and its box

  • z[i] = length of the longest stretch starting at i that matches the start of s. In "aabxaab", z[4] = 3.
  • Glue s = p + "$" + t. Wherever z[i] == m, the pattern starts at text index i − m − 1. The $ stops every match, so z[i] never exceeds m.
  • The box [l, r) is the earlier match that reaches furthest right. Inside it, s copies its own beginning, so for i < r start from min(r − i, z[i − l]) and only extend past r.
  • Every successful extension moves r right and r never moves back, so all extensions together cost O(n + m).

By hand: pattern aab, text aabaab

i 0 1 2 3 4 5 6 7 8 9
s a a b $ a a b a a b
z – 1 0 0 3 1 0 3 1 0
  • z[4] = 3 = m: a match at 4 − 3 − 1 = 0; the box becomes [4, 7).
  • i = 5 is inside the box: it mirrors i = 1, so start from z[1] = 1, no re-reading.
  • z[7] = 3: a match at 3. Answer [0, 3].

Solution 2 in Java: the Z-algorithm

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        String s = p + "$" + t;
        int n = s.length(), m = p.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
            if (z[i] == m) res.add(i - m - 1);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("abracadabra", "abra"));
        System.out.println(find("namaste india, namaste world", "namaste"));
        System.out.println(find("aaaaa", "aa"));
        System.out.println(find("chai", "chai"));
        System.out.println(find("abc", "abcd"));
    }
}
[0, 7]
[0, 15]
[0, 1, 2, 3]
[0]
[]

Both big tests:

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        String s = p + "$" + t;
        int n = s.length(), m = p.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
            if (z[i] == m) res.add(i - m - 1);
        }
        return res;
    }
    public static void main(String[] args) {
        String t = "a".repeat(2000000), a = "a".repeat(1000000);
        for (String p : new String[]{a + "b", a}) {
            long t0 = System.nanoTime();
            int c = find(t, p).size();
            long ms = (System.nanoTime() - t0) / 1000000;
            System.out.println(c + " matches, " + ms + " ms");
        }
    }
}
0 matches, 95 ms
1000001 matches, 202 ms

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// Rabin-Karp: rolling hash in base B mod M, verify on every hash match.
vector<int> rabinKarp(const string& t, const string& p) {
    const long long M = 1000000007LL, B = 131;
    vector<int> res;
    int n = t.size(), m = p.size();
    if (m > n) return res;
    long long hp = 0, ht = 0, pw = 1;
    for (int k = 0; k < m; k++) {
        hp = (hp * B + p[k]) % M;
        ht = (ht * B + t[k]) % M;
        if (k > 0) pw = pw * B % M;
    }
    for (int i = 0; ; i++) {
        if (ht == hp && t.compare(i, m, p) == 0) res.push_back(i);
        if (i + m == n) break;
        ht = (ht - t[i] * pw % M + M) % M;
        ht = (ht * B + t[i + m]) % M;
    }
    return res;
}

// Z-algorithm on p + "$" + t: z[i] == m means a match at i - m - 1.
vector<int> zFind(const string& t, const string& p) {
    string s = p + "$" + t;
    int n = s.size(), m = p.size(), l = 0, r = 0;
    vector<int> z(n, 0), res;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
        if (z[i] == m) res.push_back(i - m - 1);
    }
    return res;
}

void show(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    vector<pair<string, string>> tests = {{"abracadabra", "abra"}, {"namaste india, namaste world", "namaste"},
                                          {"aaaaa", "aa"}, {"chai", "chai"}, {"abc", "abcd"}};
    for (auto& [t, p] : tests) { show(rabinKarp(t, p)); show(zFind(t, p)); }
    string big(2000000, 'a'), a(1000000, 'a');
    cout << zFind(big, a + "b").size() << " " << zFind(big, a).size() << "\n";
}
[0, 7]
[0, 7]
[0, 15]
[0, 15]
[0, 1, 2, 3]
[0, 1, 2, 3]
[0]
[0]
[]
[]
0 1000001

The same solutions in Python

def rabin_karp(t, p):
    """Rolling hash in base B mod M; verify the letters on every hash match."""
    M, B = 1_000_000_007, 131
    n, m = len(t), len(p)
    res = []
    if m > n:
        return res
    hp = ht = 0
    for k in range(m):
        hp = (hp * B + ord(p[k])) % M
        ht = (ht * B + ord(t[k])) % M
    pw = pow(B, m - 1, M)
    for i in range(n - m + 1):
        if ht == hp and t[i:i + m] == p:
            res.append(i)
        if i + m < n:
            ht = (ht - ord(t[i]) * pw) % M      # Python's % is never negative
            ht = (ht * B + ord(t[i + m])) % M
    return res


def z_find(t, p):
    """Z-algorithm on p + '$' + t: z[i] == m means a match at i - m - 1."""
    s = p + "$" + t
    n, m = len(s), len(p)
    z = [0] * n
    l = r = 0
    res = []
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
        if z[i] == m:
            res.append(i - m - 1)
    return res


tests = [("abracadabra", "abra"), ("namaste india, namaste world", "namaste"),
         ("aaaaa", "aa"), ("chai", "chai"), ("abc", "abcd")]
for t, p in tests:
    print(rabin_karp(t, p), z_find(t, p))
[0, 7] [0, 7]
[0, 15] [0, 15]
[0, 1, 2, 3] [0, 1, 2, 3]
[0] [0]
[] []

In Python, % always returns a non-negative result for a positive M, so the "+ M" trick is not needed (it is in Java and C++).

Three real bugs

Bug 1: no + M when removing the old letter. In Java, the remainder of a negative number is negative (-3 % 7 is -3), so the window hash goes negative and never equals the pattern's hash.

import java.util.*;

public class Main {
    static final long M = 1_000_000_007L, B = 131;
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return res;
        long hp = 0, ht = 0, pw = 1;
        for (int k = 0; k < m; k++) {
            hp = (hp * B + p.charAt(k)) % M;
            ht = (ht * B + t.charAt(k)) % M;
            if (k > 0) pw = pw * B % M;
        }
        for (int i = 0; ; i++) {
            if (ht == hp && t.startsWith(p, i)) res.add(i);
            if (i + m == n) break;
            ht = (ht - t.charAt(i) * pw % M) % M;
            ht = (ht * B + t.charAt(i + m)) % M;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("namaste india, namaste world", "namaste"));
    }
}
[0]

Bug 2: int instead of long. A hash is up to about a billion; times 131 is over 100 billion, far past Integer.MAX_VALUE (2,147,483,647). It overflows, and the second namaste is lost.

import java.util.*;

public class Main {
    static final int M = 1_000_000_007, B = 131;
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        int n = t.length(), m = p.length();
        if (m > n) return res;
        int hp = 0, ht = 0, pw = 1;
        for (int k = 0; k < m; k++) {
            hp = (hp * B + p.charAt(k)) % M;
            ht = (ht * B + t.charAt(k)) % M;
            if (k > 0) pw = pw * B % M;
        }
        for (int i = 0; ; i++) {
            if (ht == hp && t.startsWith(p, i)) res.add(i);
            if (i + m == n) break;
            ht = (ht - t.charAt(i) * pw % M + M) % M;
            ht = (ht * B + t.charAt(i + m)) % M;
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("namaste india, namaste world", "namaste"));
    }
}
[0]

Bug 3: no $ separator in the Z-algorithm. The match runs on past the pattern into the text, z grows bigger than m, and z[i] == m misses real matches.

import java.util.*;

public class Main {
    static List<Integer> find(String t, String p) {
        List<Integer> res = new ArrayList<>();
        String s = p + t;
        int n = s.length(), m = p.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
            if (z[i] == m) res.add(i - m);
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(find("aaaaa", "aa"));
    }
}
[3]

Expected [0, 1, 2, 3].

Complexity

Approach Time Extra space Big input (n = 2 million, m = 1 million)
Letter by letter O(n × m) worst O(1) Time Limit Exceeded
Sum fingerprint O(n + m) O(1) fast but wrong (anagrams)
Rabin-Karp O(n + m) + O(m) per hash match O(1) no matches: 30 ms; a million matches: Time Limit Exceeded
Z-algorithm O(n + m) always O(n + m) both cases: about 0.1 to 0.2 s
KMP (episode 80) O(n + m) always O(m) same as Z

Common mistakes

Mistake What you see (real) Why Fix
Sum of the letters as the hash [0, 7] for "listen" in "listen silent" a sum ignores order positional hash in base B
(ht - x) % M [0] instead of [0, 15] Java's % keeps the minus sign (ht - x + M) % M
int hashes [0] instead of [0, 15] ht * B overflows int long, and % M after each step
No verification on a hash match a rare false match two windows can share a remainder t.startsWith(p, i)
s = p + t in Z [3] instead of [0, 1, 2, 3] z can grow past m s = p + "$" + t
Loop i + m < n instead of stopping at i + m == n the last window is never checked off by one check, then break when i + m == n

Mini project: search your own chat export

Read a text file line by line, join it into one string, and print every match of a word typed by the user with the 20 letters around it (like Ctrl+F's preview). Add a flag to ignore case (lower-case both strings first) and time Rabin-Karp against the Z-algorithm on a file of a few megabytes.

Practice

1. Find the Index of the First Occurrence in a String (LeetCode 28). Return the first match or −1.

2. Longest Happy Prefix (LeetCode 1392). The longest prefix that is also a suffix: the first i with i + z[i] == n.

3. Shortest Palindrome (LeetCode 214). Add the fewest letters in front: find the longest palindromic prefix with the Z-array of s + "$" + reverse(s).

4. The Z-array of "aaaaa" by hand.

Solutions
import java.util.*;

public class Main {
    static int[] zArray(String s) {
        int n = s.length(), l = 0, r = 0;
        int[] z = new int[n];
        for (int i = 1; i < n; i++) {
            if (i < r) z[i] = Math.min(r - i, z[i - l]);
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
            if (i + z[i] > r) { l = i; r = i + z[i]; }
        }
        return z;
    }
    // LeetCode 28: index of the first occurrence, or -1.
    static int strStr(String haystack, String needle) {
        String s = needle + "$" + haystack;
        int[] z = zArray(s);
        int m = needle.length();
        for (int i = m + 1; i < s.length(); i++)
            if (z[i] == m) return i - m - 1;
        return -1;
    }
    // LeetCode 1392: longest prefix that is also a suffix (not the whole string).
    static String longestPrefix(String s) {
        int[] z = zArray(s);
        for (int i = 1; i < s.length(); i++)
            if (i + z[i] == s.length()) return s.substring(i);
        return "";
    }
    // LeetCode 214: shortest palindrome by adding letters in front.
    static String shortestPalindrome(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        String g = s + "$" + rev;
        int[] z = zArray(g);
        int n = s.length(), keep = 0;
        for (int i = n + 1; i < g.length(); i++)
            if (i + z[i] == g.length()) { keep = g.length() - i; break; }
        return rev.substring(0, n - keep) + s;
    }
    public static void main(String[] args) {
        System.out.println(strStr("sadbutsad", "sad"));
        System.out.println(strStr("leetcode", "leeto"));
        System.out.println(longestPrefix("level"));
        System.out.println(longestPrefix("ababab"));
        System.out.println(shortestPalindrome("aacecaaa"));
        System.out.println(shortestPalindrome("abcd"));
        System.out.println(Arrays.toString(zArray("aaaaa")));
    }
}
0
-1
l
abab
aaacecaaa
dcbabcd
[0, 4, 3, 2, 1]

Quick quiz

String s = "abcxabcd"; What is z[4]? A) 3 B) 4 C) 0 D) 8

Answer

A) 3. From index 4 we read a, b, c, which match s[0..2]; then d ≠ x.

Interview questions

  1. Why does a plain sum make a bad hash? It ignores order: anagrams collide.
  2. How does the rolling hash slide in O(1)? Subtract the old letter times B^(m−1), multiply by B, add the new letter, all mod M.
  3. Why verify on a hash match? Different strings can share a hash modulo M; verification makes the answer always correct.
  4. What is Rabin-Karp's worst case? O(n × m), when there are many (real or colliding) hash matches to verify.
  5. What does z[i] mean, and how does it find a pattern? The longest match with the prefix starting at i; in p + "$" + t, z[i] == m marks a match.
  6. Why is the Z-algorithm linear? Every successful comparison moves the box's right end r forward, and r never moves back.
  7. When is hashing better than Z or KMP? Comparing many substrings (repeated substrings, many patterns of one length, 2D matching), often with binary search.

Glossary

Term Meaning
String matching Finding every place a pattern occurs in a text
Window The m letters of the text starting at i
Hash / fingerprint One number computed from a string
Collision Two different strings with the same hash
Anagram The same letters in a different order
Base B How much each place is worth compared with the next
Rolling hash A hash updated in O(1) as the window slides
Modulo M The remainder after dividing by M, keeps numbers small
Place value B^(m−1): what the window's first letter contributes
Verify Compare the letters after the hashes match
Rabin-Karp Rolling hash + verification
Z-array z[i]: longest match with the prefix, starting at i
Separator A character in neither string, like $
Z-box [l, r) The earlier match reaching furthest right
Overflow An int past 2³¹ − 1 wraps to a wrong value
Linear time O(n + m)

Summary

  • Letter by letter is O(n × m): two million letters time out.
  • A fingerprint per window, slid in O(1), avoids re-reading; a sum collides, so read the window as a number in base B, mod M.
  • Rabin-Karp: hash, slide, verify on a match. Fast on average, but O(n × m) when there are very many matches.
  • Z-algorithm: p + "$" + t, z[i] == m is a match, and the box makes it O(n + m) guaranteed.
  • In Java, add M before % after subtracting, hash in long, and never forget the separator.
  • Next episode: segment tree: range sum with point updates.