Java KMP Knuth Morris Pratt String Matching Algorithm

Introduction

The java kmp algorithm for string matching, named after Donald Knuth, James Morris, and Vaughan Pratt, finds all occurrences of a pattern in a text in linear time, beating the naive O(n times m) approach by exploiting the structure of the pattern itself. The algorithm was published in 1977 in the SIAM Journal on Computing paper "Fast Pattern Matching in Strings", with Knuth at Stanford, Morris at CMU, and Pratt at MIT. Knuth credits the idea to Morris's 1970 PhD thesis and to independent discoveries by Matiyasevich in 1969 in Soviet mathematics, so the algorithm is sometimes called the Knuth Morris Pratt Matiyasevich algorithm.

For a Java learner, the java kmp algorithm is the gateway to understanding how preprocessing a pattern can speed up matching. The naive approach slides the pattern one character at a time along the text, restarting from the start of the pattern on every mismatch, which wastes work. KMP precomputes a prefix function, also called the failure function, that tells the algorithm how far to slide the pattern on a mismatch without missing any occurrence. The result is O(n plus m) time, where n is the text length and m is the pattern length, which is optimal in the worst case.

What is KMP?

KMP is a string matching algorithm that uses a prefix function to skip ahead on partial matches. It belongs to the family of exact string matching algorithms alongside the Boyer Moore algorithm and the Rabin Karp algorithm. KMP is the simplest of the three to implement and analyse, and it is the only one with a guaranteed linear worst case bound on every input.

The prefix function pi of a pattern P is an array where pi[i] is the length of the longest proper prefix of the substring P[0 to i] that is also a suffix of that substring. A proper prefix is a prefix that is shorter than the whole string, so we never compare the whole substring with itself. The prefix function captures the internal repetition structure of the pattern, which is exactly what KMP exploits to skip ahead on mismatches.

The asymptotic cost is O(m) to compute the prefix function and O(n) to walk the text, giving O(n plus m) total. The walk never moves the text pointer backwards, which is the key insight that distinguishes KMP from the naive approach. The pattern pointer can move backwards, but only along the prefix function, which is bounded by m, so the total pattern pointer movement is O(n plus m) by amortised analysis.

How KMP Works - Step by Step

Step 1: Compute the prefix function pi for the pattern. Walk the pattern from left to right with two pointers: the pattern index i from 1 to m minus 1, and the matched length k starting at zero. For each i, while k is greater than zero and P[k] is not equal to P[i], set k to pi[k minus 1]. If P[k] equals P[i], increment k. Set pi[i] to k.

Step 2: Walk the text with two pointers: the text index j from 0 to n minus 1, and the matched length k starting at zero. For each j, while k is greater than zero and P[k] is not equal to T[j], set k to pi[k minus 1]. If P[k] equals T[j], increment k. If k equals m, we have found an occurrence at position j minus m plus 1, and we set k to pi[m minus 1] to continue searching for overlapping occurrences.

Step 3: The while loop in Step 2 is what makes KMP linear. The matched length k never exceeds the pattern length m, and it increases by at most 1 per iteration of the for loop, so it can decrease by at most n times in total. The total work of the while loop across the entire for loop is O(n), which is the amortised argument that gives KMP its linear time bound.

Step 4: The prefix function construction in Step 1 follows the same amortised argument. The matched length k increases by at most 1 per iteration of the for loop, so the total work of the while loop is O(m). The total preprocessing cost is therefore O(m), which is the same as a single pass over the pattern.

Step 5: The output is a list of starting positions of all occurrences of the pattern in the text. For a pattern of length m and a text of length n, the list has at most n minus m plus 1 entries, and KMP can find all of them in O(n plus m) time, which is optimal.

Java Program for KMP

import java.util.ArrayList;
import java.util.List;

public class KMPDemo {

    // Computes the prefix function (also called the failure function)
    // of the pattern. pi[i] is the length of the longest proper prefix
    // of pattern[0..i] that is also a suffix of pattern[0..i].
    public static int[] computePrefix(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int k = 0;
        for (int i = 1; i < m; i++) {
            while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
                k = pi[k - 1];
            }
            if (pattern.charAt(k) == pattern.charAt(i)) {
                k++;
            }
            pi[i] = k;
        }
        return pi;
    }

    // Returns the starting positions of all occurrences of pattern in text.
    public static List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        if (pattern.isEmpty()) {
            return result;
        }
        int[] pi = computePrefix(pattern);
        int n = text.length();
        int m = pattern.length();
        int k = 0;
        for (int j = 0; j < n; j++) {
            while (k > 0 && pattern.charAt(k) != text.charAt(j)) {
                k = pi[k - 1];
            }
            if (pattern.charAt(k) == text.charAt(j)) {
                k++;
            }
            if (k == m) {
                result.add(j - m + 1);
                k = pi[k - 1];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABABABABCABAB";
        String pattern = "ABABCABAB";
        List<Integer> positions = search(text, pattern);
        System.out.println("Text:    " + text);
        System.out.println("Pattern: " + pattern);
        System.out.println("Occurrences at positions: " + positions);

        String text2 = "AABAACAADAABAABA";
        String pattern2 = "AABA";
        List<Integer> positions2 = search(text2, pattern2);
        System.out.println("Text:    " + text2);
        System.out.println("Pattern: " + pattern2);
        System.out.println("Occurrences at positions: " + positions2);
    }
}

Code Explanation - Line by Line

The computePrefix method builds the pi array in one left to right pass over the pattern. The variable k is the length of the current matched prefix, which is also the index of the next pattern character we expect to match. The for loop walks i from 1 to m minus 1, and at each step, the while loop adjusts k by following the pi pointers backwards until either k reaches zero or the pattern character at k matches the pattern character at i.

The key insight is that following pi[k minus 1] gives the next longest prefix that could match, because pi[k minus 1] is the length of the longest proper prefix of the prefix of length k that is also a suffix. By induction, this is the longest possible next match length, so the while loop finds the correct k in amortised O(1) per iteration.

The search method walks the text in a single pass with the same structure as the prefix function construction. The variable k is the length of the current match, and the for loop walks j from 0 to n minus 1. The while loop adjusts k on a mismatch by following pi[k minus 1] backwards, exactly as in the prefix function. When k equals m, the pattern is fully matched, so we record the starting position j minus m plus 1 and reset k to pi[m minus 1] to find overlapping occurrences.

The reset to pi[m minus 1] is what allows KMP to find overlapping occurrences. The pattern ABABCABAB has the property that the prefix ABAB of length 4 is also a suffix, so after a full match at position p, the next match can start at position p plus 5 rather than p plus 9, because the suffix ABAB of the previous match overlaps with the prefix ABAB of the next match.

The main method runs two test cases. The first uses the classic Knuth Morris Pratt example pattern ABABCABAB, which has a rich prefix function because of the ABAB repetition. The second uses the simpler pattern AABA, which has a smaller but still useful prefix function. Both tests confirm that KMP finds all occurrences including overlapping ones.

Sample Input and Output

Input:  Text:    ABABDABACDABABCABABABABCABAB
        Pattern: ABABCABAB

Output: Occurrences at positions: [10, 18]

Input:  Text:    AABAACAADAABAABA
        Pattern: AABA

Output: Occurrences at positions: [0, 9, 12]

The first output shows two occurrences of ABABCABAB in the text. The first starts at position 10, the second at position 18. The gap of 8 between them is less than the pattern length of 9, which means the occurrences overlap by one character, which is the classic KMP example that the naive algorithm handles but does so by wasting work. The second output shows three occurrences of AABA, including two overlapping occurrences at positions 9 and 12 in AABAABA, which share the middle AB.

Common Mistakes to Avoid

First, do not confuse pi[k minus 1] with pi[k]. The while loop must follow pi[k minus 1] because k is one past the last matched character, so the longest proper prefix of the matched prefix of length k is pi[k minus 1]. Using pi[k] would skip too far and miss occurrences.

Second, do not forget to reset k to pi[m minus 1] after a full match. Without the reset, KMP finds only the first occurrence and misses overlapping occurrences. The reset to pi[m minus 1] is the same as the while loop adjustment on a virtual mismatch at position m, which is the correct way to find overlapping occurrences.

Third, do not use the naive O(n times m) approach as a fallback for short patterns. KMP is always at most O(n plus m), which is at most O(n) for short patterns, so it is never slower than the naive approach in the asymptotic sense. The naive approach is only faster on average for patterns with rare mismatches, where the constant factors of the naive inner loop beat the prefix function overhead.

Fourth, do not build the prefix function by comparing the pattern with itself using a nested loop. That gives O(m squared) preprocessing, which destroys the linear time guarantee. The two pointer while loop construction is the only correct way to build pi in O(m).

Real-World Applications

KMP is the standard algorithm for grep like exact pattern matching when the pattern is known in advance. The GNU grep tool uses a variant of KMP for fixed string searches when Boyer Moore is not faster, and the ripgrep tool uses the Rust regex engine which includes a KMP like DFA construction for fixed strings.

In bioinformatics, KMP is used to find restriction enzyme sites and motif occurrences in DNA sequences. The Aho Corasick algorithm, which generalises KMP to multiple patterns by building a trie with failure links, is the standard tool for finding all occurrences of every pattern in a database simultaneously.

In compiler construction, KMP is the basis for the longest prefix match in lexical analysers. The flex tool generates a DFA that combines the prefix function of every lexeme into a single state machine, which is essentially the Aho Corasick extension of KMP applied to the set of language keywords.

In version control systems, KMP is used in diff algorithms to find common substrings between two versions of a file. The Myers diff algorithm uses KMP internally to find the longest common subsequence of lines, which is the basis of the unified diff output that git produces.

Conclusion

We built KMP with a prefix function computed in O(m) by a two pointer while loop, and a single text pass in O(n) using the same while loop pattern. We learned that the prefix function captures the internal repetition structure of the pattern, that following pi[k minus 1] on a mismatch is the key to linear time, and that the reset to pi[m minus 1] after a full match finds overlapping occurrences. Next, study the Boyer Moore algorithm for the variant that skips more characters by scanning the pattern right to left, and the Aho Corasick algorithm for the multi pattern extension.