Knuth-Morris-Pratt (KMP) Algorithm for String Searching

Understanding the KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is a highly efficient string searching algorithm that finds occurrences of a 'pattern' within a 'text'. Unlike naive approaches that can re-compare many characters after a mismatch, KMP uses a precomputed 'Longest Proper Prefix' (LPS) array to make intelligent shifts, avoiding redundant comparisons. This makes it a popular topic in technical interviews for its clever optimization.

Example: KMP Algorithm Implementation

Here is a Python implementation of the KMP algorithm. The process involves two main parts: computing the LPS array and then performing the search using this array.

# Function to compute the Longest Proper Prefix (LPS) array
def compute_lps_array(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0  # Length of the previous longest prefix suffix
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

# Function to implement KMP search
def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    lps = compute_lps_array(pattern)
    i = 0  # pointer for text
    j = 0  # pointer for pattern
    indices = []

    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            indices.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return indices

# Example Usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = kmp_search(text, pattern)
print(f"Pattern found at indices: {result}") # Output: Pattern found at indices: [10]

text2 = "AAAAABAAABA"
pattern2 = "AAAA"
result2 = kmp_search(text2, pattern2)
print(f"Pattern found at indices: {result2}") # Output: Pattern found at indices: [0, 1]