KMP (Knuth-Morris-Pratt) algorithm is a substring search algorithm.
LPS: Longest proper Prefix which is also Suffix. For example, "abcdeabc" has the LPS "abc". Note that the string itself can't be an LPS of itself.
Algorithm
Generate the LPS array.
Take advantage of the LPS array so that once we find a mismatch, we can efficiently jump to an earlier point and continue searching.
For the pattern string t we are searching, the lps array is of the same length as t. lps[i] is the length of LPS of t[0..i].
Example:
t = a b a b x a b a b x g
lps = 0 0 1 2 0 1 2 3 4 5 0
Implementation
// OJ: https://leetcode.com/problems/implement-strstr/
// Author: github.com/lzl124631x
// Time: O(M+N)
// Space: O(N)
class Solution {
vector<int> getLps(string &s) {
int N = s.size(), i = 0;
vector<int> lps(N); // lps[0] is always 0
for (int j = 1; j < N; ++j) {
while (i > 0 && s[i] != s[j]) i = lps[i - 1]; // when s[i] can't match s[j], keep moving `i` backwards to `lps[i-1]`
i += s[i] == s[j]; // Move `i` if s[j] matches s[i]
lps[j] = i; // Assign the matched length to lps[j]
}
return lps;
}
public:
int strStr(string s, string t) {
if (t.empty()) return 0;
int M = s.size(), N = t.size(), i = 0, j = 0;
auto lps = getLps(t);
while (i < M) {
if (s[i] == t[j]) { // if match, move i and j once
++i;
++j;
if (j == N) return i - N; // Full match found.
} else {
if (j) j = lps[j - 1]; // The first lps[j-1] charaters are already matched. Start the next match from lps[j-1]
else ++i; // The first character is not matched, move i.
}
}
return -1;
}
};
Problems
KMP Count
Count the occurrence of t in string s.
// OJ: https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(M + N)
class Solution {
vector<int> getLps(string &s) {
int N = s.size(), i = 0;
vector<int> lps(N); // lps[0] is always 0
for (int j = 1; j < N; ++j) {
while (i > 0 && s[i] != s[j]) i = lps[i - 1]; // when s[i] can't match s[j], keep moving `i` backwards to `lps[i-1]`
i += s[i] == s[j]; // Move `i` if s[j] matches s[i]
lps[j] = i; // Assign the matched length to lps[j]
}
return lps;
}
int KMPCount(string s, string t) {
if (t.empty()) return 0;
int M = s.size(), N = t.size(), i = 0, j = 0, ans = 0;
auto lps = getLps(t);
while (i < M) {
if (s[i] == t[j]) {
++i;
++j;
if (j == N) {
++ans;
j = lps[j - 1]; // Full match found. Move `j` back to `lps[j-1]` to skip matched prefix
}
} else {
if (j) j = lps[j - 1];
else ++i;
}
}
return ans;
}
public:
int countMatchingSubarrays(vector<int>& A, vector<int>& P) {
int N = A.size(), M = P.size();
string s, p;
for (int i = 1; i < N; ++i) {
s.push_back(A[i] > A[i - 1] ? 'a' : (A[i] == A[i - 1] ? 'b' : 'c'));
}
for (auto &n : P) {
p.push_back(n == 1 ? 'a' : (n == 0 ? 'b' : 'c'));
}
return KMPCount(s, p);
}
};