881839. Pattern searching
Easy
Pattern Searching
Slug: pattern-searching5231--150028 Difficulty: Easy Id: 881839 Topic Tags: STL
Summary
The problem is about searching a given text for a specific pattern. The key concepts involved are string manipulation, pattern matching, and algorithmic approaches.
Detailed Explanation
To solve this problem, we can use the Knuth-Morris-Pratt (KMP) algorithm, which is an efficient way to search for a pattern in a text. The KMP algorithm preprocesses the pattern to create a lookup table that helps us skip over non-matching characters at the beginning of the text.
Here's a step-by-step breakdown of the solution:
- Preprocess the pattern to create a lookup table called
lps(longest proper prefix suffix). This table stores the length of the longest proper prefix that is also a proper suffix for each prefix of the pattern. - Initialize two pointers,
textIndexandpatternIndex, to 0. These pointers will be used to iterate through the text and the pattern respectively. - Compare the character at the current position in the text with the character at the current position in the pattern.
- If they match, move both pointers forward by 1 character.
- If they don't match, use the
lpstable to determine how many characters we can skip over in the text without losing our chance of finding the pattern. This is done by looking up the length of the longest proper prefix that is also a proper suffix for the current prefix of the pattern. - Repeat steps 3-5 until we find the pattern or reach the end of the text.
Time complexity: O(n + m), where n is the length of the text and m is the length of the pattern.
Space complexity: O(m) for the lps table.
Optimized Solutions
Java
public int search(String text, String pattern) {
int[] lps = computeLPSArray(pattern);
int textIndex = 0;
int patternIndex = 0;
while (textIndex < text.length()) {
if (pattern.charAt(patternIndex) == text.charAt(textIndex)) {
textIndex++;
patternIndex++;
}
if (patternIndex == pattern.length()) {
return textIndex - patternIndex;
}
else if (textIndex < text.length() && pattern.charAt(patternIndex) != text.charAt(textIndex)) {
if (patternIndex != 0) {
patternIndex = lps[patternIndex - 1];
} else {
textIndex++;
}
}
}
return -1;
}
private int[] computeLPSArray(String pattern) {
int[] lps = new int[pattern.length()];
int length = 0;
lps[0] = 0;
for (int i = 1; i < pattern.length(); i++) {
while (length > 0 && pattern.charAt(i) != pattern.charAt(length)) {
length = lps[length - 1];
}
if (pattern.charAt(i) == pattern.charAt(length)) {
length++;
}
lps[i] = length;
}
return lps;
}