Mastery Points
0
Pattern Matching algorithms in dsa
Context & Logic
Pattern matching is the process of finding occurrences of a pattern string within a larger text string. Common algorithms include Naive search, KMP, and Rabin-Karp.
Example
// Naive approach
function search(text, pat) {
const N = text.length, M = pat.length;
for (let i = 0; i <= N - M; i++) {
let j;
for (j = 0; j < M; j++) {
if (text[i + j] !== pat[j]) break;
}
if (j === M) return i; // Found at index i
}
return -1;
}Step-by-Step Logic
1
Iterate through the text from start to (N - M).
2
At each position, check if the subsequent characters match the pattern.
3
If a mismatch occurs, shift the pattern by one position.
4
If all characters match, return the starting index.
Complexity Metrics
Time Efficiency
Naive: O(N*M), KMP: O(N+M)
Memory Footprint
O(1) for Naive, O(M) for KMP