POI 2005 - Template - 3rd solution analysis

Problems and Contests
#1

The third solution goes over all chars of the string using KMP but potentially changes the number of matched chars so far. Shouldn’t this potentially change the analysis of the amortized complexity of KMP whenever most candidates are incorrect?

Here is the relevant function from the solution (should be O(N)):

int shortest_template(int n) {

	if (!p[n - 1]) return n;

	int cand = shortest_template(p[n - 1]);

	for (int i = p[n - 1], j = cand, curr = p[n - 1] - 1; i < n; i++) {

		while (j && (j == cand || s[i] != s[j])) j = p[j - 1];

		if (s[i] == s[j]) j++;


		if (j == cand) curr = i;

		if (i - curr >= cand) return n;

	}

	return cand;

}
#2

The only part of the code that looks like it could potentially cause the portion of shortest_template outside the recursive call to run in \omega(n-p[n-1]) time is the line while (j && (j == cand || s[i] != s[j])) j = p[j - 1];. But this turns out not to be a problem because:

  1. j must equal cand when i=p[n-1] as well as when i=n.
  2. j increases at most n - p[n-1] times
  3. Every time the while loop evaluates to true, j decreases. So the while loop can evaluate to true at most n-p[n-1] times.