Pattern Matching Basics
Pattern matching is finding occurrences of a substring (pattern) within a larger text. The most straightforward approach is the brute-force (naive) method, which checks every possible starting position.
Naive Pattern Matching
Time complexity: O(n*m) worst case (n = text length, m = pattern length).
public static int naiveSearch(String text, String pattern) {
int n = text.length(), m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) break;
}
if (j == m) return i; // found at index i
}
return -1;
}
KMP (Knuth-Morris-Pratt) Algorithm
KMP improves to O(n+m) by preprocessing the pattern to create a "partial match" table (LPS array). It avoids re-checking characters that have already been matched.
This is a classic algorithm that appears in interviews. For now, understand the naive method; KMP is covered in advanced pattern matching sections.
Two Minute Drill
- Pattern matching finds occurrences of a substring within a text.
- Naive method: O(n*m) time, simple to implement.
- KMP algorithm improves to O(n+m) using LPS array.
- Pattern matching is fundamental in text processing and bioinformatics.
Need more clarification?
Drop us an email at career@quipoinfotech.com