SyntaxPilot
Courses/DSA and Coding Problems/Lesson 80
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 80 of 90

String matching: KMP

queued

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 i where t[i..i+m-1] equals p.
  • 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 index i of a String.
  • 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 of p[0..i].
  • Fall back: after a mismatch with j letters matched, set j = 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,001 starts, and at each one the first 500,000 letters match before the b fails: about 250 billion letter compares. O(n · m).
  • After a mismatch, the start moves by one and i + j goes 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

  1. Build lps for the pattern.
  2. For each text letter t[i], with j letters matched: while (j > 0 && t[i] != p[j]) j = lps[j − 1]; then if (t[i] == p[j]) j++;
  3. When j == m: record i − m + 1, then j = 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

  1. Why is naive matching O(n · m)? Up to n − m + 1 shifts, each comparing up to m letters; inputs like aaaa… with aaa…ab hit it.
  2. What does lps[i] mean? The length of the longest proper prefix of p[0..i] that is also a suffix of it.
  3. 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.
  4. Why is KMP linear even with a nested while? Amortised: j rises at most n times, and each fallback lowers it.
  5. How do you get overlapping matches? After a full match, set j = lps[m − 1], not 0.
  6. How do you build the LPS array, and in what time? Match the pattern against itself with the same fallback rule; O(m).
  7. Other uses of the LPS array? The period of a string (n − lps[n − 1]), repeated substring pattern, shortest palindrome, counting prefix occurrences.
  8. 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 million as.
  • It re-reads letters it already matched; the matched part tells us where the pattern can fit next.
  • lps[i] = longest proper prefix of p[0..i] that is also its suffix; build it once in O(m).
  • Mismatch: j = lps[j − 1] (in a while loop); match: record i − m + 1, then j = 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.