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