Hard
Total and per-character cost of KMP's failure-link loop
This is the search phase of Knuth-Morris-Pratt, with the failure table already built for a pattern of length m. For a text of length n, what is the worst-case total work, counting every iteration of the inner while loop?
main.cpp
// fail[q] = length of the longest proper prefix of p[0..q]
// that is also a suffix of p[0..q]
int countMatches(const string& t, const string& p, const vector<int>& fail) {
int count = 0, q = 0; // q = number of pattern chars currently matched
for (size_t i = 0; i < t.size(); i++) {
while (q > 0 && p[q] != t[i]) q = fail[q - 1];
if (p[q] == t[i]) q++;
if (q == (int)p.size()) { count++; q = fail[q - 1]; }
}
return count;
}42 of 46 in Data Structures & Algorithms