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, lengthn) and the short one we search for (p, lengthm). - Window: the
mletters of the text starting at indexi, the candidate place for a match. - Overlapping matches: matches that share letters, like
"aa"at 0 and 1 in"aaaaa". - Character code: every
charis 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,
31is3 × 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 primeMso they stay small. - Prime: a number with no divisors except 1 and itself.
1,000,000,007is 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 atithat 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
intresult past2³¹ − 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 + 1starts we compare up tomletters: 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 − 1letters, 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 atithat matches the start ofs. In"aabxaab",z[4] = 3.- Glue
s = p + "$" + t. Whereverz[i] == m, the pattern starts at text indexi − m − 1. The$stops every match, soz[i]never exceedsm. - The box
[l, r)is the earlier match that reaches furthest right. Inside it,scopies its own beginning, so fori < rstart frommin(r − i, z[i − l])and only extend pastr. - Every successful extension moves
rright andrnever 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 at4 − 3 − 1 = 0; the box becomes[4, 7).i = 5is inside the box: it mirrorsi = 1, so start fromz[1] = 1, no re-reading.z[7] = 3: a match at3. 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
- Why does a plain sum make a bad hash? It ignores order: anagrams collide.
- How does the rolling hash slide in O(1)? Subtract the old letter times
B^(m−1), multiply byB, add the new letter, all modM. - Why verify on a hash match? Different strings can share a hash modulo
M; verification makes the answer always correct. - What is Rabin-Karp's worst case? O(n × m), when there are many (real or colliding) hash matches to verify.
- What does
z[i]mean, and how does it find a pattern? The longest match with the prefix starting ati; inp + "$" + t,z[i] == mmarks a match. - Why is the Z-algorithm linear? Every successful comparison moves the box's right end
rforward, andrnever moves back. - 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] == mis a match, and the box makes it O(n + m) guaranteed. - In Java, add
Mbefore%after subtracting, hash inlong, and never forget the separator. - Next episode: segment tree: range sum with point updates.