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;
}
```