AntInLoop

Knuth–Morris–Pratt (KMP) Algorithm Code Implementations

Complete Knuth–Morris–Pratt (KMP) Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Knuth–Morris–Pratt (KMP) Algorithm Guide · Launch Interactive Visualizer

C++ Implementation

// KMP (Knuth-Morris-Pratt) Algorithm Implementation in C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <chrono>

class KMPAlgorithm {
public:
    // Compute the Longest Proper Prefix which is also Suffix (LPS) array
    static std::vector<int> computeLPS(const std::string& pattern) {
        std::vector<int> lps(pattern.length(), 0);
        int len = 0; // Length of the previous longest prefix suffix
        int i = 1;
        
        while (i < pattern.length()) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    // KMP Search Algorithm
    static std::vector<int> kmpSearch(const std::string& text, const std::string& pattern) {
        int n = text.length();
        int m = pattern.length();
        std::vector<int> lps = computeLPS(pattern);
        std::vector<int> matches;
        
        int i = 0; // Index for text
        int j = 0; // Index for pattern
        
        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            
            if (j == m) {
                // Pattern found at index i - j
                matches.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    // KMP with case-insensitive search
    static std::vector<int> kmpSearchCaseInsensitive(std::string text, std::string pattern) {
        // Convert to lowercase
        std::transform(text.begin(), text.end(), text.begin(), ::tolower);
        std::transform(pattern.begin(), pattern.end(), pattern.begin(), ::tolower);
        return kmpSearch(text, pattern);
    }
    
    // KMP with multiple pattern search
    static std::unordered_map<std::string, std::vector<int>> kmpMultiplePatterns(
        const std::string& text, const std::vector<std::string>& patterns) {
        std::unordered_map<std::string, std::vector<int>> results;
        
        for (const auto& pattern : patterns) {
            results[pattern] = kmpSearch(text, pattern);
        }
        
        return results;
    }
    
    // KMP with replacement
    static std::string kmpReplace(const std::string& text, const std::string& pattern, 
                                 const std::string& replacement) {
        std::vector<int> matches = kmpSearch(text, pattern);
        if (matches.empty()) return text;
        
        std::string result;
        int lastIndex = 0;
        
        for (int matchIndex : matches) {
            result += text.substr(lastIndex, matchIndex - lastIndex);
            result += replacement;
            lastIndex = matchIndex + pattern.length();
        }
        
        result += text.substr(lastIndex);
        return result;
    }
    
    // KMP with count only
    static int kmpCount(const std::string& text, const std::string& pattern) {
        return kmpSearch(text, pattern).size();
    }
    
    // KMP with first occurrence only
    static int kmpFirstMatch(const std::string& text, const std::string& pattern) {
        std::vector<int> matches = kmpSearch(text, pattern);
        return matches.empty() ? -1 : matches[0];
    }
    
    // KMP with last occurrence only
    static int kmpLastMatch(const std::string& text, const std::string& pattern) {
        std::vector<int> matches = kmpSearch(text, pattern);
        return matches.empty() ? -1 : matches[matches.size() - 1];
    }
    
    // KMP with overlapping matches
    static std::vector<int> kmpSearchOverlapping(const std::string& text, const std::string& pattern) {
        int n = text.length();
        int m = pattern.length();
        std::vector<int> lps = computeLPS(pattern);
        std::vector<int> matches;
        
        int i = 0;
        int j = 0;
        
        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.push_back(i - j);
                j = lps[j - 1]; // Don't reset j to 0 for overlapping
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    // KMP with performance measurement
    struct KMPResult {
        std::vector<int> matches;
        int count;
        long long executionTime;
        
        KMPResult(const std::vector<int>& m, int c, long long t) 
            : matches(m), count(c), executionTime(t) {}
    };
    
    static KMPResult kmpSearchWithTiming(const std::string& text, const std::string& pattern) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> matches = kmpSearch(text, pattern);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        return KMPResult(matches, matches.size(), duration.count());
    }
    
    // KMP with detailed analysis
    struct KMPAnalysis {
        std::string pattern;
        int patternLength;
        int textLength;
        std::vector<int> lpsArray;
        std::vector<int> matches;
        int matchCount;
        std::unordered_map<std::string, std::string> efficiency;
        
        KMPAnalysis(const std::string& p, int pLen, int tLen, const std::vector<int>& lps,
                   const std::vector<int>& m, int mCount) 
            : pattern(p), patternLength(pLen), textLength(tLen), lpsArray(lps), 
              matches(m), matchCount(mCount) {
            efficiency["comparisons"] = std::to_string(tLen + pLen);
            efficiency["time_complexity"] = "O(n + m)";
            efficiency["space_complexity"] = "O(m)";
        }
    };
    
    static KMPAnalysis kmpAnalyze(const std::string& text, const std::string& pattern) {
        std::vector<int> lps = computeLPS(pattern);
        std::vector<int> matches = kmpSearch(text, pattern);
        
        return KMPAnalysis(pattern, pattern.length(), text.length(), lps, matches, matches.size());
    }
    
    // Additional utilities
    static bool kmpIsSubstring(const std::string& text, const std::string& pattern) {
        return !kmpSearch(text, pattern).empty();
    }
    
    static std::string kmpLongestCommonSubstring(const std::string& str1, const std::string& str2) {
        // This is a simplified version - full LCS would need different algorithm
        std::string result = "";
        int maxLength = 0;
        
        for (int i = 0; i < str1.length(); i++) {
            for (int j = i + 1; j <= str1.length(); j++) {
                std::string substring = str1.substr(i, j - i);
                if (kmpIsSubstring(str2, substring) && substring.length() > maxLength) {
                    maxLength = substring.length();
                    result = substring;
                }
            }
        }
        
        return result;
    }
    
    // Performance comparison
    static void comparePerformance(const std::string& text, const std::string& pattern) {
        auto start = std::chrono::high_resolution_clock::now();
        std::vector<int> matches = kmpSearch(text, pattern);
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        std::cout << "KMP Search: " << matches.size() << " matches found in " 
                  << duration.count() << " μs" << std::endl;
    }
};

JAVA Implementation

// KMP (Knuth-Morris-Pratt) Algorithm Implementation in Java

import java.util.*;

public class KMPAlgorithm {
    // Compute the Longest Proper Prefix which is also Suffix (LPS) array
    public static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0; // Length of the previous longest prefix suffix
        int i = 1;
        
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    // KMP Search Algorithm
    public static List<Integer> kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPS(pattern);
        List<Integer> matches = new ArrayList<>();
        
        int i = 0; // Index for text
        int j = 0; // Index for pattern
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            
            if (j == m) {
                // Pattern found at index i - j
                matches.add(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    // KMP with case-insensitive search
    public static List<Integer> kmpSearchCaseInsensitive(String text, String pattern) {
        return kmpSearch(text.toLowerCase(), pattern.toLowerCase());
    }
    
    // KMP with multiple pattern search
    public static Map<String, List<Integer>> kmpMultiplePatterns(String text, String[] patterns) {
        Map<String, List<Integer>> results = new HashMap<>();
        
        for (String pattern : patterns) {
            results.put(pattern, kmpSearch(text, pattern));
        }
        
        return results;
    }
    
    // KMP with replacement
    public static String kmpReplace(String text, String pattern, String replacement) {
        List<Integer> matches = kmpSearch(text, pattern);
        if (matches.isEmpty()) return text;
        
        StringBuilder result = new StringBuilder();
        int lastIndex = 0;
        
        for (int matchIndex : matches) {
            result.append(text.substring(lastIndex, matchIndex));
            result.append(replacement);
            lastIndex = matchIndex + pattern.length();
        }
        
        result.append(text.substring(lastIndex));
        return result.toString();
    }
    
    // KMP with count only
    public static int kmpCount(String text, String pattern) {
        return kmpSearch(text, pattern).size();
    }
    
    // KMP with first occurrence only
    public static int kmpFirstMatch(String text, String pattern) {
        List<Integer> matches = kmpSearch(text, pattern);
        return matches.isEmpty() ? -1 : matches.get(0);
    }
    
    // KMP with last occurrence only
    public static int kmpLastMatch(String text, String pattern) {
        List<Integer> matches = kmpSearch(text, pattern);
        return matches.isEmpty() ? -1 : matches.get(matches.size() - 1);
    }
    
    // KMP with overlapping matches
    public static List<Integer> kmpSearchOverlapping(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPS(pattern);
        List<Integer> matches = new ArrayList<>();
        
        int i = 0;
        int j = 0;
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            
            if (j == m) {
                matches.add(i - j);
                j = lps[j - 1]; // Don't reset j to 0 for overlapping
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return matches;
    }
    
    // KMP with performance measurement
    public static class KMPResult {
        public List<Integer> matches;
        public int count;
        public long executionTime;
        
        public KMPResult(List<Integer> matches, int count, long executionTime) {
            this.matches = matches;
            this.count = count;
            this.executionTime = executionTime;
        }
    }
    
    public static KMPResult kmpSearchWithTiming(String text, String pattern) {
        long startTime = System.nanoTime();
        List<Integer> matches = kmpSearch(text, pattern);
        long endTime = System.nanoTime();
        
        return new KMPResult(matches, matches.size(), endTime - startTime);
    }
    
    // KMP with detailed analysis
    public static class KMPAnalysis {
        public String pattern;
        public int patternLength;
        public int textLength;
        public int[] lpsArray;
        public List<Integer> matches;
        public int matchCount;
        public Map<String, String> efficiency;
        
        public KMPAnalysis(String pattern, int patternLength, int textLength, 
                          int[] lpsArray, List<Integer> matches, int matchCount) {
            this.pattern = pattern;
            this.patternLength = patternLength;
            this.textLength = textLength;
            this.lpsArray = lpsArray;
            this.matches = matches;
            this.matchCount = matchCount;
            
            this.efficiency = new HashMap<>();
            this.efficiency.put("comparisons", String.valueOf(textLength + patternLength));
            this.efficiency.put("time_complexity", "O(n + m)");
            this.efficiency.put("space_complexity", "O(m)");
        }
    }
    
    public static KMPAnalysis kmpAnalyze(String text, String pattern) {
        int[] lps = computeLPS(pattern);
        List<Integer> matches = kmpSearch(text, pattern);
        
        return new KMPAnalysis(pattern, pattern.length(), text.length(), 
                              lps, matches, matches.size());
    }
    
    // Additional utilities
    public static boolean kmpIsSubstring(String text, String pattern) {
        return !kmpSearch(text, pattern).isEmpty();
    }
    
    public static String kmpLongestCommonSubstring(String str1, String str2) {
        // This is a simplified version - full LCS would need different algorithm
        String result = "";
        int maxLength = 0;
        
        for (int i = 0; i < str1.length(); i++) {
            for (int j = i + 1; j <= str1.length(); j++) {
                String substring = str1.substring(i, j);
                if (kmpIsSubstring(str2, substring) && substring.length() > maxLength) {
                    maxLength = substring.length();
                    result = substring;
                }
            }
        }
        
        return result;
    }
}

JAVASCRIPT Implementation

// KMP (Knuth-Morris-Pratt) Algorithm Implementation in JavaScript

// Compute the Longest Proper Prefix which is also Suffix (LPS) array
function computeLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0; // Length of the previous longest prefix suffix
  let i = 1;
  
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  
  return lps;
}

// KMP Search Algorithm
function kmpSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const lps = computeLPS(pattern);
  const matches = [];
  
  let i = 0; // Index for text
  let j = 0; // Index for pattern
  
  while (i < n) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }
    
    if (j === m) {
      // Pattern found at index i - j
      matches.push(i - j);
      j = lps[j - 1];
    } else if (i < n && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  
  return matches;
}

// KMP with case-insensitive search
function kmpSearchCaseInsensitive(text, pattern) {
  const lowerText = text.toLowerCase();
  const lowerPattern = pattern.toLowerCase();
  return kmpSearch(lowerText, lowerPattern);
}

// KMP with multiple pattern search
function kmpMultiplePatterns(text, patterns) {
  const results = {};
  
  for (const pattern of patterns) {
    results[pattern] = kmpSearch(text, pattern);
  }
  
  return results;
}

// KMP with wildcard support (simplified)
function kmpWithWildcards(text, pattern) {
  // Replace wildcards with a special character
  const processedPattern = pattern.replace(/\*/g, '\0');
  const matches = kmpSearch(text, processedPattern);
  
  // Filter matches that actually work with wildcards
  return matches.filter(startIndex => {
    let patternIndex = 0;
    let textIndex = startIndex;
    
    while (patternIndex < pattern.length && textIndex < text.length) {
      if (pattern[patternIndex] === '*' || pattern[patternIndex] === text[textIndex]) {
        patternIndex++;
        textIndex++;
      } else if (pattern[patternIndex] === '*') {
        patternIndex++;
      } else {
        return false;
      }
    }
    
    return patternIndex === pattern.length;
  });
}

// KMP with replacement
function kmpReplace(text, pattern, replacement) {
  const matches = kmpSearch(text, pattern);
  if (matches.length === 0) return text;
  
  let result = '';
  let lastIndex = 0;
  
  for (const matchIndex of matches) {
    result += text.slice(lastIndex, matchIndex);
    result += replacement;
    lastIndex = matchIndex + pattern.length;
  }
  
  result += text.slice(lastIndex);
  return result;
}

// KMP with count only
function kmpCount(text, pattern) {
  const matches = kmpSearch(text, pattern);
  return matches.length;
}

// KMP with first occurrence only
function kmpFirstMatch(text, pattern) {
  const matches = kmpSearch(text, pattern);
  return matches.length > 0 ? matches[0] : -1;
}

// KMP with last occurrence only
function kmpLastMatch(text, pattern) {
  const matches = kmpSearch(text, pattern);
  return matches.length > 0 ? matches[matches.length - 1] : -1;
}

// KMP with overlapping matches
function kmpSearchOverlapping(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const lps = computeLPS(pattern);
  const matches = [];
  
  let i = 0;
  let j = 0;
  
  while (i < n) {
    if (pattern[j] === text[i]) {
      i++;
      j++;
    }
    
    if (j === m) {
      matches.push(i - j);
      j = lps[j - 1]; // Don't reset j to 0 for overlapping
    } else if (i < n && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  
  return matches;
}

// KMP with performance measurement
function kmpSearchWithTiming(text, pattern) {
  const startTime = performance.now();
  const matches = kmpSearch(text, pattern);
  const endTime = performance.now();
  
  return {
    matches,
    count: matches.length,
    executionTime: endTime - startTime
  };
}

// KMP with detailed analysis
function kmpAnalyze(text, pattern) {
  const lps = computeLPS(pattern);
  const matches = kmpSearch(text, pattern);
  
  return {
    pattern,
    patternLength: pattern.length,
    textLength: text.length,
    lpsArray: lps,
    matches,
    matchCount: matches.length,
    efficiency: {
      comparisons: text.length + pattern.length,
      timeComplexity: 'O(n + m)',
      spaceComplexity: 'O(m)'
    }
  };
}

PYTHON Implementation

# KMP (Knuth-Morris-Pratt) Algorithm Implementation in Python

def compute_lps(pattern):
    """Compute the Longest Proper Prefix which is also Suffix (LPS) array"""
    lps = [0] * len(pattern)
    length = 0  # Length of the previous longest prefix suffix
    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

def kmp_search(text, pattern):
    """KMP Search Algorithm"""
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)
    matches = []
    
    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:
            # Pattern found at index i - j
            matches.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 matches

def kmp_search_case_insensitive(text, pattern):
    """KMP with case-insensitive search"""
    return kmp_search(text.lower(), pattern.lower())

def kmp_multiple_patterns(text, patterns):
    """KMP with multiple pattern search"""
    results = {}
    for pattern in patterns:
        results[pattern] = kmp_search(text, pattern)
    return results

def kmp_with_wildcards(text, pattern):
    """KMP with wildcard support (simplified)"""
    import re
    # Convert pattern to regex
    regex_pattern = pattern.replace('*', '.*')
    matches = []
    
    for match in re.finditer(regex_pattern, text):
        matches.append(match.start())
    
    return matches

def kmp_replace(text, pattern, replacement):
    """KMP with replacement"""
    matches = kmp_search(text, pattern)
    if not matches:
        return text
    
    result = ""
    last_index = 0
    
    for match_index in matches:
        result += text[last_index:match_index]
        result += replacement
        last_index = match_index + len(pattern)
    
    result += text[last_index:]
    return result

def kmp_count(text, pattern):
    """KMP with count only"""
    return len(kmp_search(text, pattern))

def kmp_first_match(text, pattern):
    """KMP with first occurrence only"""
    matches = kmp_search(text, pattern)
    return matches[0] if matches else -1

def kmp_last_match(text, pattern):
    """KMP with last occurrence only"""
    matches = kmp_search(text, pattern)
    return matches[-1] if matches else -1

def kmp_search_overlapping(text, pattern):
    """KMP with overlapping matches"""
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)
    matches = []
    
    i = 0
    j = 0
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            matches.append(i - j)
            j = lps[j - 1]  # Don't reset j to 0 for overlapping
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return matches

def kmp_search_with_timing(text, pattern):
    """KMP with performance measurement"""
    import time
    start_time = time.time()
    matches = kmp_search(text, pattern)
    end_time = time.time()
    
    return {
        'matches': matches,
        'count': len(matches),
        'execution_time': end_time - start_time
    }

def kmp_analyze(text, pattern):
    """KMP with detailed analysis"""
    lps = compute_lps(pattern)
    matches = kmp_search(text, pattern)
    
    return {
        'pattern': pattern,
        'pattern_length': len(pattern),
        'text_length': len(text),
        'lps_array': lps,
        'matches': matches,
        'match_count': len(matches),
        'efficiency': {
            'comparisons': len(text) + len(pattern),
            'time_complexity': 'O(n + m)',
            'space_complexity': 'O(m)'
        }
    }

# Additional utilities
def kmp_find_all_substrings(text, pattern):
    """Find all occurrences of pattern in text"""
    return kmp_search(text, pattern)

def kmp_is_substring(text, pattern):
    """Check if pattern is a substring of text"""
    return len(kmp_search(text, pattern)) > 0

def kmp_longest_common_substring(str1, str2):
    """Find longest common substring using KMP-like approach"""
    # This is a simplified version - full LCS would need different algorithm
    max_length = 0
    result = ""
    
    for i in range(len(str1)):
        for j in range(i + 1, len(str1) + 1):
            substring = str1[i:j]
            if kmp_is_substring(str2, substring) and len(substring) > max_length:
                max_length = len(substring)
                result = substring
    
    return result