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