KMP String Matching

Share

Find all starting indices of pattern in text using Knuth-Morris-Pratt algorithm.

Example 1
Input: text="AABAACAADAABAABA", pattern="AABA" → Output: [0,9,12]
Example 2
Input: text="abcabc", pattern="abc" → Output: [0,3]

Solution Approach

Build failure function (partial match table), then scan text using the table for efficient matching.

  • Build lps[] (longest proper prefix which is also suffix) for pattern
  • i=0 (text), j=0 (pattern)
  • Match: i++, j++; at j==m: record index, j=lps[j-1]
  • Mismatch: if j>0 set j=lps[j-1] else i++
  • Return all match positions
Java
public List<Integer> kmpSearch(String text, String pattern) {
    List<Integer> result = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    int[] lps = new int[m];
    // Build LPS
    for (int i = 1, len = 0; i < m; ) {
        if (pattern.charAt(i) == pattern.charAt(len)) lps[i++] = ++len;
        else if (len > 0) len = lps[len-1];
        else lps[i++] = 0;
    }
    // Search
    for (int i = 0, j = 0; i < n; ) {
        if (text.charAt(i) == pattern.charAt(j)) { i++; j++; }
        if (j == m) { result.add(i - j); j = lps[j-1]; }
        else if (i < n && text.charAt(i) != pattern.charAt(j)) {
            if (j > 0) j = lps[j-1]; else i++;
        }
    }
    return result;
}
  • Time Complexity: O(n+m)
  • Space Complexity: O(m)