☕ DSA Java Articles

Topics › Strings › Hard String Problems

KMP Algorithm or LPS array

Hard TUF ID 977 A2ZSDE

Java source ↗ Edit this article ↗

Problem

A border of a string is a proper prefix that is also a suffix: "ab" is a border of "abcab". For a string s of length n, the LPS array (longest proper prefix which is also suffix, also called the prefix function or the pi array) stores, for every i, the length of the longest border of the prefix s[0..i].

The task has two parts:

  1. Compute the LPS array of a string.
  2. Use it to run the Knuth-Morris-Pratt (KMP) search: given text and pattern, return every 0-based index where pattern occurs in text, including overlapping occurrences.

Constraints: 0 ≤ n ≤ 10^5. An empty pattern, or one longer than the text, gives an empty list.

Example 1

s = "aabaaab"
lps = [0, 1, 0, 1, 2, 2, 3]
// lps[5] = 2: "aabaaa" starts and ends with "aa", but "aab" is not a suffix of it
// lps[6] = 3: "aabaaab" starts and ends with "aab"

Example 2

text = "aaaaa", pattern = "aa"
answer = [0, 1, 2, 3]       // overlapping matches all count

Approach 1: Brute force

Intuition. For the LPS array, follow the definition: for each prefix s[0..i], try border lengths from the longest possible (i, since the border must be proper) down to 1, and take the first one where the prefix of that length equals the suffix of that length. For the search, compare the pattern with every window of the text from scratch.

Algorithm.

  1. For each i, for len = i, i - 1, ..., 1: if s[0..len) equals s[i-len+1..i], set lps[i] = len and stop.
  2. Search: for every start i with i + m ≤ n, compare pattern with text[i..i+m) character by character.
static int[] lpsBrute(String s) {
    int n = s.length();
    int[] lps = new int[n];
    for (int i = 0; i < n; i++) {
        for (int len = i; len >= 1; len--) {           // proper: at most i for the prefix s[0..i] of length i + 1
            if (s.regionMatches(0, s, i - len + 1, len)) {
                lps[i] = len;
                break;
            }
        }
    }
    return lps;
}

static List<Integer> searchBrute(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    if (m == 0) return res;
    for (int i = 0; i + m <= n; i++) {
        int k = 0;
        while (k < m && text.charAt(i + k) == pattern.charAt(k)) k++;
        if (k == m) res.add(i);
    }
    return res;
}

Complexity. The LPS brute force is O(n^3) in the worst case (n prefixes, up to n lengths, up to n characters per comparison). The search is O(n · m): on text = "aaaa...a", pattern = "aa...ab" almost every alignment reads nearly the whole pattern before failing. Space O(n) for the array, O(1) extra for the search.

The search wastes work because after a long partial match it throws away everything it learned and restarts one position later.

Approach 2: Optimal, the prefix function and KMP

Intuition for the LPS array. Suppose we know len = lps[i-1]: the prefix s[0..len) is the longest border of s[0..i-1]. To get a border of s[0..i], a border of s[0..i-1] must be extended by the character s[i].

Intuition for the search. Run the same process with the text in place of the second copy of the string. Keep j, the number of pattern characters matched so far. On a match, increase j. On a mismatch, do not move the text pointer back; instead shift the pattern so that its longest border lines up with what was just matched, by setting j = lps[j - 1]. Those j characters are already known to match, so nothing is re-read. After a full match, record it and continue from j = lps[m - 1] so that overlapping occurrences are found.

Algorithm.

  1. LPS: len = 0. For i = 1 .. n - 1: while len > 0 and s[i] != s[len], set len = lps[len - 1]; if s[i] == s[len], increment len; store lps[i] = len.
  2. Search: j = 0. For each text index i: fall back while j > 0 and text[i] != pattern[j]; if they match, increment j; if j == m, record i - m + 1 and set j = lps[m - 1].
static int[] lpsOptimal(String s) {
    int n = s.length();
    int[] lps = new int[n];
    int len = 0;                                       // length of the border of s[0..i-1]
    for (int i = 1; i < n; i++) {
        while (len > 0 && s.charAt(i) != s.charAt(len)) len = lps[len - 1];
        if (s.charAt(i) == s.charAt(len)) len++;
        lps[i] = len;
    }
    return lps;
}

static List<Integer> searchKmp(String text, String pattern) {
    List<Integer> res = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    if (m == 0 || m > n) return res;
    int[] lps = lpsOptimal(pattern);
    int j = 0;                                         // number of pattern characters matched so far
    for (int i = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = lps[j - 1];
        if (text.charAt(i) == pattern.charAt(j)) j++;
        if (j == m) {
            res.add(i - m + 1);
            j = lps[m - 1];                            // keep the border so overlapping matches are found
        }
    }
    return res;
}

Dry run of the LPS computation on s = "aabaaab":

i s[i] len before fallbacks lps[i]
1 a 0 none, s[0] matches 1
2 b 1 1 → 0, s[0] still differs 0
3 a 0 none, s[0] matches 1
4 a 1 none, s[1] matches 2
5 a 2 s[2] = b differs, 2 → 1, then s[1] matches 2
6 b 2 none, s[2] matches 3

Complexity. Time O(n) for the LPS array and O(n + m) for the search. The argument is amortised: len (or j) increases by at most 1 per character, and every fallback decreases it by at least 1. It never goes below 0, so the total number of fallbacks cannot exceed the total number of increases, which is at most the length of the string scanned. Space O(m) for the pattern’s LPS array.

Edge cases and pitfalls