KMP

Knuth-Morris-Pratt (KMP) is a linear-time pattern matching algorithm. It preprocesses the search pattern to construct a Longest Prefix Suffix (LPS) table. The LPS table allows the search to bypass redundant character comparisons when a mismatch occurs, preventing backtracking on the main text.

Complexity Profile

Case	Complexity
Best Case	O(N + M)
Average Case	O(N + M)
Worst Case	O(N + M)
Space Complexity	O(M)

Code Implementation

def kmp_search(text, pattern):
    lps = compute_lps(pattern)
    i = j = 0
    
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            return i - j  # Pattern match index
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

def compute_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
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

Real-World Applications

• Text editors locating keyword occurrences.
• DNA sequence scanning and bio-informatics pattern matching.
• Log scanners monitoring regex occurrences in streams.