KMP Pattern Matching Algorithm

Problem

The Knuth-Morris-Pratt (KMP) algorithm finds every occurrence of a pattern in a text in linear time, by precomputing how much the pattern can safely shift after a mismatch.

Input:  text = "ababcababcabc", pattern = "abcabc"
Output: [7]   (pattern starts at index 7)

Python Solution

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    lps = build_lps(pattern)
    result = []
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                result.append(i - j)
                j = lps[j - 1]
        elif j > 0:
            j = lps[j - 1]
        else:
            i += 1
    return result

C++ Solution

vector<int> buildLPS(string& pattern) {
    vector<int> lps(pattern.size(), 0);
    int length = 0, i = 1;
    while (i < pattern.size()) {
        if (pattern[i] == pattern[length]) {
            lps[i++] = ++length;
        } else if (length > 0) {
            length = lps[length - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

vector<int> kmpSearch(string text, string pattern) {
    vector<int> lps = buildLPS(pattern);
    vector<int> result;
    int i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++; j++;
            if (j == pattern.size()) {
                result.push_back(i - j);
                j = lps[j - 1];
            }
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return result;
}

Java Solution

class Solution {
    private int[] buildLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int length = 0, i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                lps[i++] = ++length;
            } else if (length > 0) {
                length = lps[length - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }

    public List<Integer> kmpSearch(String text, String pattern) {
        int[] lps = buildLPS(pattern);
        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++; j++;
                if (j == pattern.length()) {
                    result.add(i - j);
                    j = lps[j - 1];
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return result;
    }
}

Complexity

Time: O(n + m) — building the LPS (longest proper prefix that is also a suffix) array takes O(m), and the search itself takes O(n), since the text pointer never moves backward. Space: O(m) for the LPS array.