These are the notes for DSA episode 80. You search a family WhatsApp group for "biryani": find every place a pattern appears inside a huge text. We try every start and compare letter by letter (correct, then Time Limit Exceeded on a million letters), see that it throws away the letters it already matched, and invent the LPS array (longest proper prefix that is also a suffix) that tells us how far to fall back. That is the Knuth-Morris-Pratt (KMP) algorithm: O(n + m), and the text pointer never moves back. Then three real bugs: lost overlapping matches, a StringIndexOutOfBoundsException, and a false match. 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 family group chat | In code |
|---|---|
| Years of messages | the text t, length n |
| The word in the search box ("biryani") | the pattern p, length m |
| Every highlighted place | every start index where p occurs in t |
| "Instant, whatever the chat looks like" | a worst case of O(n + m), not O(n · m) |
The same problem sits behind every editor's find box, a browser's Ctrl+F, grep over log files, and searching for a gene in DNA.
Every word, from zero
- String: a sequence of characters, like
"biryani". - Text / pattern: the long string we search in, and the short one we search for.
- Index: a position in a string, counted from 0. In
"abc",'c'is at index 2. - Match (occurrence): an index
iwheret[i..i+m-1]equalsp. - Overlapping matches: matches that share letters:
"aa"occurs in"aaaaa"at 0, 1, 2 and 3. charAt(i): Java's way to read the letter at indexiof aString.- Shift: where the pattern is lined up against the text (its first letter sits under
t[shift]). - Brute force (naive matching): try every shift and compare letter by letter.
- Prefix: a start of a string (
"ab"is a prefix of"abab"). Suffix: an end of it ("ab"is also a suffix of"abab"). - Proper prefix / suffix: one that is not the whole string.
- Border: a string that is both a proper prefix and a suffix.
- LPS array (prefix function, failure function):
lps[i]= length of the longest border ofp[0..i]. - Fall back: after a mismatch with
jletters matched, setj = lps[j − 1]and compare the same text letter again. - KMP: Knuth-Morris-Pratt, the matching algorithm built on the LPS array (published 1977).
- Amortised analysis: counting the total work over the whole run instead of the worst single step.
Problem statement
Given a text t and a pattern p, return the list of every index where p starts in t, in increasing order (overlaps included). A pattern longer than the text, or an empty pattern, gives an empty list (our rule; LeetCode 28 returns 0 for an empty needle). n can be 1,000,000.
| Call | Answer | Why |
|---|---|---|
find("ababcabcabababd", "ababd") |
[10] |
one occurrence |
find("aaaaa", "aa") |
[0, 1, 2, 3] |
overlapping |
find("abc", "abcd") |
[] |
pattern longer than text |
find("abc", "abc") |
[0] |
pattern = text |
find("abc", "") |
[] |
empty pattern |
Obvious idea: try every start
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 j = 0;
while (j < m && t.charAt(i + j) == p.charAt(j)) j++;
if (j == m) res.add(i);
}
return res;
}
public static void main(String[] args) {
System.out.println(find("ababcabcabababd", "ababd"));
System.out.println(find("aaaaa", "aa"));
System.out.println(find("abc", "abcd"));
System.out.println(find("abc", "abc"));
}
}
[10]
[0, 1, 2, 3]
[]
[0]
Correct. Now the nasty input: a text of a million as, and a pattern of 500,000 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 j = 0;
while (j < m && t.charAt(i + j) == p.charAt(j)) j++;
if (j == m) res.add(i);
}
return res;
}
public static void main(String[] args) {
String t = "a".repeat(1000000);
String p = "a".repeat(500000) + "b";
long t0 = System.nanoTime();
List<Integer> r = find(t, p);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(r.size() + " matches, " + ms + " ms");
}
}
Time limit exceeded
(Run locally with timeout 25: killed after 25 seconds, no output.)
Why is it slow?
- There are
n − m + 1 = 500,001starts, and at each one the first 500,000 letters match before thebfails: about 250 billion letter compares.O(n · m). - After a mismatch, the start moves by one and
i + jgoes back in the text, to letters it has already read. It knew exactly what they were, and forgot. - Goal: read each text letter once; the text index never goes back.
The key insight: reuse what you matched
Text abababd, pattern ababd:
| Step | What happens |
|---|---|
| shift 0 | a b a b match, then a ≠ d at index 4 |
| naive | move to shift 1, go back to index 1: b ≠ a, wasted |
| insight | the letters we read, abab, end with ab, and the pattern starts with ab |
| KMP | jump to shift 2 with j = 2 (2 letters already matched), compare index 4 again |
| result | a, b, d match: found at index 2; the text index never moved back |
How far to jump depends only on the pattern: after matching j letters, the longest border of p[0..j−1] is lps[j − 1], so continue with j = lps[j − 1].
The LPS array
lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of p[0..i].
p |
a | b | a | b | d |
|---|---|---|---|---|---|
lps |
0 | 0 | 1 | 2 | 0 |
By hand: aabaaab
| i | letter | what happens | lps[i] |
|---|---|---|---|
| 0 | a | always 0 | 0 |
| 1 | a | a = p[0], len 1 |
1 |
| 2 | b | b ≠ p[1], len = lps[0] = 0; b ≠ p[0] |
0 |
| 3 | a | a = p[0], len 1 |
1 |
| 4 | a | a = p[1], len 2 |
2 |
| 5 | a | a ≠ p[2], len = lps[1] = 1; a = p[1], len 2 |
2 |
| 6 | b | b = p[2], len 3 (aab starts and ends the pattern) |
3 |
Building the table is the matching idea run on the pattern against itself.
The KMP recipe
- Build
lpsfor the pattern. - For each text letter
t[i], withjletters matched:while (j > 0 && t[i] != p[j]) j = lps[j − 1];thenif (t[i] == p[j]) j++; - When
j == m: recordi − m + 1, thenj = lps[j − 1](so overlaps are found).
Solution in Java
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static List<Integer> find(String t, String p) {
List<Integer> res = new ArrayList<>();
int m = p.length();
if (m == 0) return res;
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == m) {
res.add(i - m + 1);
j = lps[j - 1];
}
}
return res;
}
public static void main(String[] args) {
System.out.println(find("ababcabcabababd", "ababd"));
System.out.println(find("aaaaa", "aa"));
System.out.println(find("abc", "abcd"));
System.out.println(find("abc", "abc"));
System.out.println(find("abc", ""));
}
}
[10]
[0, 1, 2, 3]
[]
[0]
[]
The million as that timed out:
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static List<Integer> find(String t, String p) {
List<Integer> res = new ArrayList<>();
int m = p.length();
if (m == 0) return res;
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == m) {
res.add(i - m + 1);
j = lps[j - 1];
}
}
return res;
}
public static void main(String[] args) {
String t = "a".repeat(1000000);
String p = "a".repeat(500000) + "b";
long t0 = System.nanoTime();
List<Integer> r = find(t, p);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(r.size() + " matches, " + ms + " ms");
}
}
0 matches, 67 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of it.
vector<int> buildLps(const string& p) {
int m = p.size(), len = 0;
vector<int> lps(m, 0);
for (int i = 1; i < m; i++) {
while (len > 0 && p[i] != p[len]) len = lps[len - 1];
if (p[i] == p[len]) len++;
lps[i] = len;
}
return lps;
}
vector<int> find(const string& t, const string& p) {
vector<int> res;
int m = p.size();
if (m == 0) return res;
vector<int> lps = buildLps(p);
for (int i = 0, j = 0; i < (int)t.size(); i++) {
while (j > 0 && t[i] != p[j]) j = lps[j - 1];
if (t[i] == p[j]) j++;
if (j == m) {
res.push_back(i - m + 1);
j = lps[j - 1];
}
}
return res;
}
void show(const vector<int>& v) {
cout << "[";
for (size_t k = 0; k < v.size(); k++) cout << (k ? ", " : "") << v[k];
cout << "]\n";
}
int main() {
show(find("ababcabcabababd", "ababd"));
show(find("aaaaa", "aa"));
show(find("abc", "abcd"));
show(find("abc", "abc"));
show(find("abc", ""));
string t(1000000, 'a'), p = string(500000, 'a') + "b";
auto t0 = chrono::steady_clock::now();
vector<int> r = find(t, p);
auto ms = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - t0).count();
cout << r.size() << " matches, " << ms << " ms\n";
}
[10]
[0, 1, 2, 3]
[]
[0]
[]
0 matches, 4 ms
The same solution in Python
import time
def build_lps(p):
"""lps[i] = length of the longest proper prefix of p[:i+1] that is also its suffix."""
m, length = len(p), 0
lps = [0] * m
for i in range(1, m):
while length > 0 and p[i] != p[length]:
length = lps[length - 1]
if p[i] == p[length]:
length += 1
lps[i] = length
return lps
def find(t, p):
res, m = [], len(p)
if m == 0:
return res
lps = build_lps(p)
j = 0
for i, ch in enumerate(t):
while j > 0 and ch != p[j]:
j = lps[j - 1]
if ch == p[j]:
j += 1
if j == m:
res.append(i - m + 1)
j = lps[j - 1]
return res
print(find("ababcabcabababd", "ababd"))
print(find("aaaaa", "aa"))
print(find("abc", "abcd"))
print(find("abc", "abc"))
print(find("abc", ""))
t, p = "a" * 1_000_000, "a" * 500_000 + "b"
t0 = time.perf_counter()
r = find(t, p)
print(len(r), "matches,", int((time.perf_counter() - t0) * 1000), "ms")
[10]
[0, 1, 2, 3]
[]
[0]
[]
0 matches, 185 ms
Three real bugs
Bug 1: j = 0 after a match. It looks like "start fresh", but it skips overlapping matches.
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static List<Integer> find(String t, String p) {
List<Integer> res = new ArrayList<>();
int m = p.length();
if (m == 0) return res;
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == m) {
res.add(i - m + 1);
j = 0;
}
}
return res;
}
public static void main(String[] args) {
System.out.println(find("ababcabcabababd", "ababd"));
System.out.println(find("aaaaa", "aa"));
}
}
[10]
[0, 2]
[0, 2] instead of [0, 1, 2, 3]. Fix: j = lps[j - 1];.
Bug 2: no empty pattern check. With p = "", the first compare reads p.charAt(0) on a string with no letters.
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static List<Integer> find(String t, String p) {
List<Integer> res = new ArrayList<>();
int m = p.length();
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == m) {
res.add(i - m + 1);
j = lps[j - 1];
}
}
return res;
}
public static void main(String[] args) {
System.out.println(find("abc", ""));
}
}
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
at java.base/jdk.internal.util.Preconditions$1.apply(Preconditions.java:55)
...
at java.base/java.lang.String.charAt(String.java:1544)
at Main.find(Main.java:20)
at Main.main(Main.java:29)
Fix: if (m == 0) return res; before anything else.
Bug 3: if instead of while for the fallback. One fallback is not always enough.
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static List<Integer> find(String t, String p) {
List<Integer> res = new ArrayList<>();
int m = p.length();
if (m == 0) return res;
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
if (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == m) {
res.add(i - m + 1);
j = lps[j - 1];
}
}
return res;
}
public static void main(String[] args) {
System.out.println(find("aabaa", "aaa"));
}
}
[2]
A false match: the text at index 2 is baa, not aaa. At the b, j was 2; one fallback made it lps[1] = 1, and it stopped there instead of falling back to 0. The leftover j = 1 then counted the b position as part of a match. Fix: while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];.
Complexity
| Approach | Time | Extra space | 1,000,000 as, pattern a…ab |
|---|---|---|---|
| Try every start | O(n · m) worst case | O(1) | Time Limit Exceeded (~250 billion compares) |
| KMP | O(n + m) | O(m) for lps |
67 ms in Java |
Why linear with a while inside? j goes up by at most 1 per text letter, so it rises at most n times in total. Every fallback lowers j by at least 1, and j never goes below 0, so all fallbacks together take at most n steps. Same argument for building lps in O(m).
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Try every start on a big input | Time limit exceeded |
re-reads the text: O(n · m) | KMP |
j = 0 after a match |
[0, 2] instead of [0, 1, 2, 3] |
overlapping matches are skipped | j = lps[j - 1] |
| No empty pattern check | java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 |
p.charAt(0) on "" |
if (m == 0) return res; |
if instead of while |
[2] (a false match) |
one fallback is not always enough | while (j > 0 && ...) |
lps[0] = 1 or a non-proper border |
infinite loop / wrong jumps | the whole string is not a proper prefix | start the loop at i = 1, lps[0] = 0 |
Start index i - m |
every index off by one | the match ends at i, so it starts at i - m + 1 |
i - m + 1 |
Mini project: the chat search counter
Count how many times a word appears in each message of a chat (ignoring case), building the LPS array once and reusing it for every message.
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
static int count(String t, String p, int[] lps) {
int c = 0;
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == p.length()) { c++; j = lps[j - 1]; }
}
return c;
}
public static void main(String[] args) {
String[] chat = {
"Mummy: Who is bringing the Biryani on Sunday?",
"Papa: I will get chicken biryani from the corner shop",
"Asha: veg BIRYANI for me please, and raita",
"Ravi: biryani biryani biryani!!",
"Neha: I'll bring gulab jamun"
};
String word = "biryani";
int[] lps = buildLps(word); // built once, reused for every message
int total = 0;
for (String msg : chat) {
int c = count(msg.toLowerCase(), word, lps);
if (c > 0) System.out.println(c + " " + msg);
total += c;
}
System.out.println("total: " + total);
}
}
1 Mummy: Who is bringing the Biryani on Sunday?
1 Papa: I will get chicken biryani from the corner shop
1 Asha: veg BIRYANI for me please, and raita
3 Ravi: biryani biryani biryani!!
total: 6
Extend it: print each message with the matches wrapped in [ ], and search for several words at once.
Practice
1. Find the Index of the First Occurrence in a String (LeetCode 28). Return the first match, or -1. Stop as soon as j == m.
2. Repeated Substring Pattern (LeetCode 459). Is s a block repeated two or more times? With b = lps[n − 1], the answer is b > 0 && n % (n − b) == 0.
3. Shortest Palindrome (LeetCode 214). Add the fewest letters in front of s to make a palindrome. Run lps on s + "#" + reverse(s): its last value is the longest palindromic prefix.
4. Build lps for "abacabab" by hand. Answer: 0 0 1 0 1 2 3 2 (at the last b, len 3 fails on c, falls back to lps[2] = 1, and b = p[1] gives 2).
Solutions (1, 2, 3 and 4)
import java.util.*;
public class Main {
static int[] buildLps(String p) {
int m = p.length(), len = 0;
int[] lps = new int[m];
for (int i = 1; i < m; i++) {
while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
if (p.charAt(i) == p.charAt(len)) len++;
lps[i] = len;
}
return lps;
}
// 1. LeetCode 28: index of the first occurrence, or -1
static int strStr(String t, String p) {
if (p.isEmpty()) return 0; // LeetCode's rule for an empty needle
int[] lps = buildLps(p);
for (int i = 0, j = 0; i < t.length(); i++) {
while (j > 0 && t.charAt(i) != p.charAt(j)) j = lps[j - 1];
if (t.charAt(i) == p.charAt(j)) j++;
if (j == p.length()) return i - j + 1;
}
return -1;
}
// 2. LeetCode 459: is s some block repeated 2+ times?
static boolean repeated(String s) {
int n = s.length();
if (n == 0) return false;
int border = buildLps(s)[n - 1];
return border > 0 && n % (n - border) == 0;
}
// 3. LeetCode 214: shortest palindrome by adding letters in front
static String shortestPalindrome(String s) {
String rev = new StringBuilder(s).reverse().toString();
int[] lps = buildLps(s + "#" + rev);
int keep = lps[lps.length - 1]; // longest palindromic prefix of s
return rev.substring(0, s.length() - keep) + s;
}
public static void main(String[] args) {
System.out.println(strStr("sadbutsad", "sad") + " " + strStr("leetcode", "leeto"));
System.out.println(repeated("abab") + " " + repeated("aba") + " " + repeated("abcabcabcabc"));
System.out.println(shortestPalindrome("aacecaaa") + " " + shortestPalindrome("abcd"));
System.out.println(Arrays.toString(buildLps("abacabab")));
}
}
0 -1
true false true
aaacecaaa dcbabcd
[0, 0, 1, 0, 1, 2, 3, 2]
Quick quiz
String p = "abcabca"; with lps = 0 0 0 1 2 3 ?. What is the last value? A) 1 B) 3 C) 4 D) 7
Answer
C) 4. "abca" is both a proper prefix and a suffix of "abcabca", and no longer border exists. It can't be 7: the prefix must be proper.
Interview questions
- Why is naive matching O(n · m)? Up to
n − m + 1shifts, each comparing up tomletters; inputs likeaaaa…withaaa…abhit it. - What does
lps[i]mean? The length of the longest proper prefix ofp[0..i]that is also a suffix of it. - Why can KMP skip shifts safely? Any shift that could still match must line up a border of the matched part; the longest border gives the nearest such shift.
- Why is KMP linear even with a nested
while? Amortised:jrises at mostntimes, and each fallback lowers it. - How do you get overlapping matches? After a full match, set
j = lps[m − 1], not 0. - How do you build the LPS array, and in what time? Match the pattern against itself with the same fallback rule; O(m).
- Other uses of the LPS array? The period of a string (
n − lps[n − 1]), repeated substring pattern, shortest palindrome, counting prefix occurrences. - KMP vs Rabin-Karp vs Z-algorithm? All linear for one pattern; Rabin-Karp uses rolling hashes (expected linear, easy for many patterns), the Z-algorithm computes match lengths against the prefix (next episode).
Glossary
| Term | Meaning |
|---|---|
| Text / pattern | The string we search in / the string we search for |
| Index | A position in a string, counted from 0 |
| Match (occurrence) | A start index where the pattern appears |
| Overlapping matches | Matches that share letters |
charAt(i) |
The letter at index i of a Java String |
| Shift | Where the pattern is lined up against the text |
| Naive matching | Try every shift, compare letter by letter |
| Prefix / suffix | A start / an end of a string |
| Proper | Not the whole string |
| Border | A proper prefix that is also a suffix |
| LPS array | lps[i] = length of the longest border of p[0..i] |
| Fall back | j = lps[j − 1] after a mismatch |
| KMP | Knuth-Morris-Pratt matching, O(n + m) |
| Amortised | Total work over the whole run, averaged per step |
StringIndexOutOfBoundsException |
Java's error for reading a string position that doesn't exist |
Summary
- Trying every start is
O(n · m)and times out on inputs like a millionas. - It re-reads letters it already matched; the matched part tells us where the pattern can fit next.
lps[i]= longest proper prefix ofp[0..i]that is also its suffix; build it once inO(m).- Mismatch:
j = lps[j − 1](in a while loop); match: recordi − m + 1, thenj = lps[j − 1]. - Check for an empty pattern first.
O(n + m)time,O(m)space; the text index never moves back.- Next episode: Rabin-Karp and the Z-algorithm.