KMP
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 lpsReal-World Applications
- Text editors locating keyword occurrences.
- DNA sequence scanning and bio-informatics pattern matching.
- Log scanners monitoring regex occurrences in streams.
Boyer-Moore
Boyer-Moore is a highly efficient string matching algorithm that serves as the standard for practical text searches. It skips comparisons by processing the pattern from right to left, utilizing the Bad Character Heuristic and Good Suffix Heuristic to shift the pattern across the text by large intervals upon character mismatches.
Trie
A Trie (Prefix Tree) is an ordered tree data structure used to store strings. Each node represents a single character, and shared prefixes share the same node paths. This allows constant time retrieval proportional to key length, regardless of dictionary size.