Compute the KMP failure function for the pattern abacabab. Then prove that the preprocessing pass runs in O(m) even though its inner loop can iterate many times on one character.

Compute the KMP failure function for the pattern abacabab. Then prove that the preprocessing pass runs in O(m) even though its inner loop can iterate many times on one character.

Approach: Fill the table position by position using the previous value, then use the length of the current border as a potential function to count total inner loop steps.

0, 0, 1, 0, 1, 2, 3, 2. The failure function at position i is the length of the longest proper border of the prefix ending at i, so for a, ab, aba, abac, abaca, abacab, abacaba, abacabab the border lengths are 0, 0, 1, 0, 1, 2, 3 and then 2, since abacabab ends in ab while the length 3 candidate aba fails at the c. The preprocessing keeps a running border length k, extends it by one when the next characters match and otherwise falls back to k = pi[k-1] until a match or zero. Use k as the potential function: it rises by at most one per position, so across m positions it rises at most m in total, and every iteration of the inner loop strictly decreases it. A quantity that increases at most m times overall and decreases by at least one per inner step can drive at most m inner steps, so the total work is O(m) even though a single character can trigger many fallbacks. The search phase has exactly the same amortised structure with the text index never moving backwards, giving O(n + m).

Follow-up: How does the failure function let you count the occurrences of every prefix of the pattern inside the text in the same pass?

Key concepts: failure function, border length, amortised analysis, potential function.