🔍 KMP Algorithm - Pattern Matching

Learn the Knuth-Morris-Pratt (KMP) algorithm for efficient string pattern matching with interactive visualization and failure function construction.

📋 Problem Statement

Given a text string and a pattern string, find all occurrences of the pattern in the text efficiently.

Example:
Text: "ABABDABACDABABCABCABCABCABC"
Pattern: "ABCABCABC"
Output: Pattern found at index 15

Why KMP? Naive pattern matching has O(nm) complexity. KMP achieves O(n+m) by avoiding redundant comparisons using a failure function.

⚙️ Configure Input

Text String:

Pattern String:

🧠 What is the Failure Function?

The Failure Function is the core preprocessing step of the KMP algorithm. It computes the length of the longest proper prefix that is also a suffix for each position in the pattern string.

📚 Definition

For position i in pattern string, failure[i] represents the length of the longest substring that is both a proper prefix and suffix of pattern[0...i] (excluding the entire string itself).

🎯 Purpose

When a mismatch occurs, tells us how many characters we can safely skip
Avoids redundant comparisons of already matched characters
Reduces time complexity from O(nm) brute force to O(n+m)

💡 Example

Pattern: A B C A B C A B C
Index:   0 1 2 3 4 5 6 7 8
Failure: 0 0 0 1 2 3 4 5 6

Explanation:
• Position 5: "ABCABC" has longest common prefix-suffix "ABC" (length 3)
• Position 8: "ABCABCABC" has longest common prefix-suffix "ABCABC" (length 6)

🏗️ Failure Function Construction

Click "Build Failure Function" to start construction

🔄 Construction Algorithm Steps

Step 1: Initialize

failure[0] = 0 (first character has no prefix)
j = 0 (tracks current prefix length)
Start iterating from i = 1 through pattern

Step 2: Handle Mismatch

If pattern[i] ≠ pattern[j] and j > 0
Set j = failure[j-1] (jump backward)
Repeat until match found or j = 0

Step 3: Update Values

If pattern[i] = pattern[j], increment j++
Set failure[i] = j
Continue to next position i++

🧮 Why Does This Work?

When pattern[i] ≠ pattern[j] at position i, we can't simply restart from scratch. Instead, we use the pre-computed failure[j-1] to jump to a potentially matching position, avoiding redundant checks of prefix parts we know will match.

🎯 Pattern Matching Visualization

Click "Start Search" to begin pattern matching

🧠 How KMP Works

1️⃣ Failure Function

Preprocesses the pattern to create an array that stores the length of the longest proper prefix which is also a suffix for each position. This helps skip unnecessary comparisons.

2️⃣ Smart Sliding

When a mismatch occurs, use the failure function to determine how far to slide the pattern, avoiding redundant character comparisons that we know will match.

3️⃣ Linear Time

Achieves O(n + m) time complexity where n is text length and m is pattern length, compared to O(nm) for naive approach.

💻 Code Implementation

Failure Function Construction

function buildFailureFunction(pattern) {
    const failure = new Array(pattern.length).fill(0);
    let j = 0; // length of previous longest prefix suffix
    
    for (let i = 1; i < pattern.length; i++) {
        while (j > 0 && pattern[i] !== pattern[j]) {
            j = failure[j - 1]; // Use failure function to jump back
        }
        
        if (pattern[i] === pattern[j]) {
            j++; // Extend the current prefix suffix
        }
        
        failure[i] = j; // Set failure value for position i
    }
    
    return failure;
}

KMP Search Algorithm

function kmpSearch(text, pattern) {
    if (pattern.length === 0) return [];
    
    const failure = buildFailureFunction(pattern);
    const matches = [];
    let j = 0; // pattern pointer
    
    for (let i = 0; i < text.length; i++) {
        // Handle mismatches using failure function
        while (j > 0 && text[i] !== pattern[j]) {
            j = failure[j - 1];
        }
        
        // If characters match, advance pattern pointer
        if (text[i] === pattern[j]) {
            j++;
        }
        
        // If we've matched the entire pattern
        if (j === pattern.length) {
            matches.push(i - j + 1); // Record starting position
            j = failure[j - 1]; // Continue searching for more matches
        }
    }
    
    return matches;
}

📈 Complexity Analysis

Time Complexity

Preprocessing: O(m) - Building failure function
Searching: O(n) - Pattern matching
Overall: O(n + m) - Linear time

Space Complexity

Failure Function: O(m) - Array of pattern length
Variables: O(1) - Constant extra space
Overall: O(m) - Linear space

🚀 Real-World Applications

🔍 Text Editors

Find and replace operations in code editors and word processors

🧬 Bioinformatics

DNA sequence matching and protein pattern recognition

🔒 Security

Intrusion detection systems and malware signature matching

🌐 Web Search

Substring search in search engines and web crawlers

KMP Algorithm - String Pattern Matching