🔍 KMP Fundamentals

🎯 What is the KMP Algorithm?

The Knuth-Morris-Pratt (KMP) algorithm is an efficient string matching algorithm that finds all occurrences of a pattern in a text. It achieves linear time by preprocessing the pattern to avoid redundant comparisons.

Inventors: Donald Knuth, James Morris, Vaughan Pratt (1977)
Key Idea: Use the prefix function (LPS) to skip characters
Time Complexity: O(n + m) where n = text length, m = pattern length
Space Complexity: O(m) for the LPS array

📌 Linear Time📌 Prefix Function📌 No Backtracking

The Core Insight

Key Insight: When a mismatch occurs, we already know the characters in the text up to that point. KMP uses this information to shift the pattern by the maximum possible amount without missing any matches.

Two Phases:

Preprocessing Build the LPS (Longest Prefix Suffix) array
Searching Scan the text using the LPS array

# KMP Algorithm - High Level Overview
def kmp_search(text, pattern):
    # Step 1: Preprocess pattern
    lps = compute_lps(pattern)
    
    # Step 2: Search
    i = 0  # index for text
    j = 0  # index for pattern
    
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == len(pattern):
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

# Example:
# text = "ABABDABACDABABCABAB"
# pattern = "ABABCABAB"
# Output: Pattern found at index 10

📝 Naive Pattern Matching

🎯 The Baseline Approach

The naive approach checks for the pattern at every possible position in the text. When a mismatch occurs, it starts over from the next position.

Time Complexity: O(n × m) worst case
Space Complexity: O(1)
Problem: Wasted comparisons (backtracking)

# Naive Pattern Matching
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    occurrences = []
    
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        
        if j == m:
            occurrences.append(i)
    
    return occurrences

# Example:
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
# Naive: Many redundant comparisons
# KMP avoids these by using the prefix function

# Worst case scenario:
# text = "AAAAAAAAAAAAAAAAAB" (n = 17)
# pattern = "AAAAB" (m = 5)
# Naive does: O(n × m) comparisons
# KMP does: O(n + m) comparisons

📐 Prefix Function (π)

🎯 Understanding π[i]

The prefix function π[i] for a string s of length m is the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i].

Proper Prefix: A prefix that is not the entire string
Proper Suffix: A suffix that is not the entire string
π[0] = 0 (empty string)
Key Property: π[i] ≤ π[i-1] + 1

Why Prefix Function?

Example: For pattern "ABABCABAB", the prefix function tells us how many characters we can skip when a mismatch occurs.

# Prefix Function Computation
def prefix_function(s):
    n = len(s)
    pi = [0] * n
    
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    
    return pi

# Example for pattern "ABABCABAB":
# s = A B A B C A B A B
# pi = 0 0 1 2 0 1 2 3 4

# Let's trace:
# i=0: pi[0] = 0
# i=1: "AB" → pi[1] = 0
# i=2: "ABA" → pi[2] = 1 ("A")
# i=3: "ABAB" → pi[3] = 2 ("AB")
# i=4: "ABABC" → pi[4] = 0
# i=5: "ABABCA" → pi[5] = 1 ("A")
# i=6: "ABABCAB" → pi[6] = 2 ("AB")
# i=7: "ABABCABA" → pi[7] = 3 ("ABA")
# i=8: "ABABCABAB" → pi[8] = 4 ("ABAB")

🎯 LPS Array Construction

🎯 LPS = Longest Prefix Suffix

The LPS array is the same as the prefix function. It's used in KMP to determine how many characters to shift the pattern after a mismatch.

LPS[i]: Length of longest proper prefix that is also a suffix
Construction: O(m) time, O(m) space
Use: When mismatch at j, set j = lps[j-1]

# LPS Array Construction (Full Implementation)
def compute_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0  # length of 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

# Example: pattern = "ABABCABAB"
def lps_example():
    pattern = "ABABCABAB"
    lps = compute_lps(pattern)
    print("Pattern:", pattern)
    print("LPS:    ", lps)
    # Output: [0, 0, 1, 2, 0, 1, 2, 3, 4]

# Understanding LPS values:
# lps[0] = 0: "A" has no proper prefix that's also suffix
# lps[1] = 0: "AB" has no proper prefix that's also suffix
# lps[2] = 1: "ABA" → "A" is both prefix and suffix
# lps[3] = 2: "ABAB" → "AB" is both prefix and suffix
# lps[4] = 0: "ABABC" → no overlap
# lps[5] = 1: "ABABCA" → "A"
# lps[6] = 2: "ABABCAB" → "AB"
# lps[7] = 3: "ABABCABA" → "ABA"
# lps[8] = 4: "ABABCABAB" → "ABAB"

🔍 KMP Search Algorithm

🎯 The Complete Algorithm

KMP uses the LPS array to efficiently search for the pattern in the text. It never backtracks in the text, ensuring O(n) time.

# Complete KMP Search
def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    
    if m == 0:
        return []
    
    # Compute LPS array
    lps = compute_lps(pattern)
    
    occurrences = []
    i = 0  # index for text
    j = 0  # index for pattern
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            occurrences.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 occurrences

# Example with step-by-step trace
def kmp_demo():
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    
    occurrences = kmp_search(text, pattern)
    print(f"Text: {text}")
    print(f"Pattern: {pattern}")
    print(f"Occurrences at indices: {occurrences}")
    
    # Output: Occurrences at indices: [10]
    
    # Step-by-step trace:
    # i=0: A matches, i=1
    # i=1: B matches, i=2
    # i=2: A matches, i=3
    # i=3: B matches, i=4
    # i=4: C vs A mismatch → j = lps[3] = 2
    # Now j=2 (pattern[2] = A), continue from i=4
    # i=4: A matches, i=5
    # ... and so on

📊 Visualization & Walkthrough

🎯 Visualizing KMP in Action

Understanding KMP is much easier with a visual walkthrough. Here's how the algorithm works on a concrete example.

# KMP Visualization - Step by Step
# Text:    A B A B D A B A C D A B A B C A B A B
# Pattern: A B A B C A B A B
# LPS:     [0, 0, 1, 2, 0, 1, 2, 3, 4]

# Step 1: Compare text[0] with pattern[0]
# A matches! i=1, j=1

# Step 2: Compare text[1] with pattern[1]
# B matches! i=2, j=2

# Step 3: Compare text[2] with pattern[2]
# A matches! i=3, j=3

# Step 4: Compare text[3] with pattern[3]
# B matches! i=4, j=4

# Step 5: Compare text[4] with pattern[4]
# D vs C → Mismatch!
# j = lps[3] = 2 (pattern[2] = A)
# Now compare text[4] with pattern[2]

# Step 6: Compare text[4] with pattern[2]
# D vs A → Mismatch!
# j = lps[1] = 0
# Now compare text[4] with pattern[0]

# Step 7: Compare text[4] with pattern[0]
# D vs A → Mismatch! j=0, i=5

# Continue until pattern found at index 10

⏱️ Time & Space Complexities

Algorithm	Time Complexity	Space Complexity	Notes
Naive	O(n × m)	O(1)	Worst case: O(n × m)
KMP	O(n + m)	O(m)	Linear time!
Z-Algorithm	O(n + m)	O(n + m)	Similar to KMP
Rabin-Karp	O(n + m) avg	O(1)	Rolling hash
Boyer-Moore	O(n) avg	O(m)	Best for large alphabets
KMP Preprocessing	O(m)	O(m)	LPS construction
KMP Search	O(n)	O(1)	After preprocessing

🌀 KMP Variations

KMP with Wildcards: Pattern matching with '?' or '*'
Multiple Patterns: Aho-Corasick (extension of KMP)
2D KMP: Pattern matching in 2D arrays
Prefix Function on Strings: Applications beyond pattern matching
KMP for Streams: Processing streaming data
KMP with Unicode: Multi-byte character support

🔤 Z-Algorithm Connection

🎯 A Related String Matching Algorithm

The Z-algorithm is another linear-time string matching algorithm. It computes the Z-array where Z[i] is the longest prefix of the combined string that matches the suffix starting at i.

Combined String: pattern + "$" + text
Z[i] = m: Pattern found at position i
Time: O(n + m) both preprocessing and search

# Z-Algorithm
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    
    return z

# KMP vs Z-Algorithm
def compare_algorithms():
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    
    # KMP
    kmp_result = kmp_search(text, pattern)
    
    # Z-Algorithm
    combined = pattern + "$" + text
    z = z_algorithm(combined)
    z_result = [i - len(pattern) - 1 for i in range(len(z)) 
                if z[i] == len(pattern)]
    
    print(f"KMP: {kmp_result}")
    print(f"Z-Algorithm: {z_result}")
    # Both should give the same result

# Key difference:
# KMP: O(m) space (LPS array)
# Z-Algorithm: O(n+m) space (Z-array)

📊 Rabin-Karp Comparison

🎯 Another String Matching Approach

Rabin-Karp uses hashing to find matches, rolling the hash for each position in the text.

Hash Function: Rolling hash (e.g., polynomial hash)
Time: O(n + m) average, O(n × m) worst
KMP vs Rabin-Karp: KMP is deterministic, Rabin-Karp has hash collisions

# Rabin-Karp Algorithm (Simplified)
def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    
    # Simple hash function (for demonstration)
    def hash_str(s):
        return sum(ord(c) for c in s)
    
    pattern_hash = hash_str(pattern)
    window_hash = hash_str(text[:m])
    occurrences = []
    
    for i in range(n - m + 1):
        if window_hash == pattern_hash:
            if text[i:i+m] == pattern:
                occurrences.append(i)
        
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) + ord(text[i + m]))
    
    return occurrences

# Comparison of algorithms
def algorithm_comparison():
    text = "ABABDABACDABABCABAB" * 100
    pattern = "ABABCABAB"
    
    import time
    
    start = time.time()
    kmp_search(text, pattern)
    kmp_time = time.time() - start
    
    start = time.time()
    rabin_karp(text, pattern)
    rk_time = time.time() - start
    
    print(f"KMP Time: {kmp_time:.6f}s")
    print(f"Rabin-Karp Time: {rk_time:.6f}s")

🚀 Boyer-Moore Comparison

🎯 Another Efficient Algorithm

Boyer-Moore is often faster in practice, especially for large alphabets. It uses the bad-character and good-suffix heuristics.

Bad-Character Heuristic: Skip based on mismatched character
Good-Suffix Heuristic: Skip based on matched suffix
Time: O(n) average, O(n × m) worst

# Comparison: KMP vs Boyer-Moore
def compare_kmp_bm():
    text = "A" * 10000 + "B"
    pattern = "A" * 5000 + "B"
    
    # KMP: Always O(n + m) = O(15000)
    # Boyer-Moore: Very fast for this case due to heuristics
    
    # When to use which:
    # KMP: Worst-case guaranteed O(n + m)
    # Boyer-Moore: Usually faster, but worst-case O(n × m)
    # Rabin-Karp: Good for multiple pattern matching
    
    # KMP is preferred when:
    # - Predictable performance is needed
    # - Pattern is short
    # - Alphabet is small (e.g., DNA sequences)
    
    # Boyer-Moore is preferred when:
    # - Pattern is long
    # - Alphabet is large (e.g., English text)
    # - Average-case performance matters more

🌍 Real-World Applications

Text Editors: Find and replace functionality
Search Engines: Pattern matching in documents
Bioinformatics: DNA sequence matching
Data Compression: LZ77 uses pattern matching
Intrusion Detection: Pattern matching in network traffic
Compiler Design: Lexical analysis
Computer Vision: Template matching
Digital Forensics: Searching for patterns in data

🧠 Advanced KMP Concepts

🎯 Beyond Basic Pattern Matching

KMP for Sets of Patterns: Aho-Corasick algorithm
KMP with Wildcards: Patterns with '?' or '*'
KMP in 2D: Pattern matching in 2D grids
KMP for Periodic Patterns: Patterns that repeat
KMP with Regular Expressions: Combining with regex

# Aho-Corasick (Multiple Pattern KMP)
# This is an extension of KMP for multiple patterns

# KMP for Wildcards (Simplified)
def kmp_wildcard(text, pattern):
    # Pattern can contain '?' (matches any single character)
    # Modify LPS computation to handle '?'
    
    def compute_lps_wildcard(pattern):
        m = len(pattern)
        lps = [0] * m
        length = 0
        i = 1
        
        while i < m:
            if pattern[i] == pattern[length] or pattern[i] == '?' or 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
    
    # Then use the modified LPS in KMP search
    # When comparing, treat '?' as matching any character

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Implement strStr() using KMP"
Pattern Matching: "Find all occurrences of pattern in text"
LPS Array: "Compute the LPS array for a given string"
Circular Pattern: "Find pattern in a circular string"
Wildcard Matching: "Pattern matching with '?' and '*'"
Anagram Matching: "Find all anagram positions in text"
Repeated Pattern: "Check if string can be formed by repeating pattern"
Prefix-Suffix: "Find longest prefix that is also suffix"

# Interview Problem: Implement strStr() using KMP
def strStr(text, pattern):
    if not pattern:
        return 0
    
    if not text or len(pattern) > len(text):
        return -1
    
    occurrences = kmp_search(text, pattern)
    return occurrences[0] if occurrences else -1

# Interview Problem: Repeated Pattern
def repeated_pattern(s):
    n = len(s)
    lps = compute_lps(s)
    length = lps[-1]
    
    # If the string can be formed by repeating a pattern
    if length > 0 and n % (n - length) == 0:
        return s[:n - length]
    return None

# Interview Problem: Count Occurrences
def count_occurrences(text, pattern):
    return len(kmp_search(text, pattern))

# Interview Problem: Longest Prefix-Suffix
def longest_prefix_suffix(s):
    lps = compute_lps(s)
    return lps[-1]  # Length of longest proper prefix that is also suffix

# Example:
# s = "aaaa"
# lps = [0, 1, 2, 3]
# longest_prefix_suffix = 3