712150. Count Substring
Count Substring
Summary
The problem is to count the number of occurrences of a given substring within a larger string. This problem involves pattern matching and requires a efficient algorithm to solve it.
Detailed Explanation
To solve this problem, we can use the KMP (Knuth-Morris-Pratt) algorithm which is an efficient way to find all occurrences of one string in another. The algorithm works by preprocessing the pattern string and then using that information to skip over parts of the text string while searching for the pattern.
Here's a step-by-step breakdown of the solution:
- Create a lookup table
lps(longest prefix suffix) of the same length as the pattern string. This table stores the length of the longest proper prefix which is also a suffix. - Iterate over the text string and at each position, use the
lpstable to determine how many characters can be skipped without missing any occurrences of the pattern. - When a match is found, increment the count of occurrences.
Here's an ASCII art diagram showing the lookup table:
1 | 2 | 3 | 4 | 5 | LPS
-------------------------
0 | 0 | 0 | 1 | 2 |
The time complexity of this algorithm is O(n + m), where n is the length of the text string and m is the length of the pattern string. The space complexity is O(m) for storing the lps table.
Optimized Solutions
Java
public class CountSubstring {
public static int countSubstr(String text, String pattern) {
int n = text.length();
int m = pattern.length();
int[] lps = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = lps[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
}
lps[i] = j;
}
int count = 0;
j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
j = lps[j - 1];
}
if (text.charAt(i) == pattern.charAt(j)) {
j++;
if (j == m) {
count++;
j = lps[j - 1];
}
}
}
return count;
}
}