Last updated
String Matching Algorithms
String matching finds occurrences of a pattern within a text. The naive approach checks every position in the text, giving O(n×m) time complexity. More efficient algorithms like KMP (Knuth-Morris-Pratt) and Boyer-Moore achieve O(n+m) by preprocessing the pattern to skip unnecessary comparisons.
Algorithm Comparison
| Algorithm | Time | Space | Best For |
|---|---|---|---|
| Naive | O(n×m) | O(1) | Short patterns, simple use |
| KMP | O(n+m) | O(m) | Repeated patterns, streaming |
| Boyer-Moore | O(n/m) best | O(σ) | Long patterns, large alphabets |
| Rabin-Karp | O(n+m) avg | O(1) | Multiple pattern search |
| Regex (NFA) | O(n×m) worst | O(m) | Complex patterns |
JavaScript String Matching
JavaScript
// Find all occurrences with positions
function findAll(text, pattern, caseSensitive = true) {
const t = caseSensitive ? text : text.toLowerCase();
const p = caseSensitive ? pattern : pattern.toLowerCase();
const results = [];
let pos = 0;
while ((pos = t.indexOf(p, pos)) !== -1) {
results.push({
index: pos,
match: text.slice(pos, pos + p.length),
context: text.slice(Math.max(0, pos-20), pos+p.length+20)
});
pos++;
}
return results;
}
// Fuzzy matching (Levenshtein distance)
function levenshtein(a, b) {
const dp = Array.from({length: a.length+1}, (_, i) =>
Array.from({length: b.length+1}, (_, j) => i || j)
);
for (let i = 1; i <= a.length; i++)
for (let j = 1; j <= b.length; j++)
dp[i][j] = a[i-1] === b[j-1]
? dp[i-1][j-1]
: 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
return dp[a.length][b.length];
}