Lesson · Strings and Pattern Matching · Preprocessing the pattern

The Amortised Bound, as a Count

“Amortised” is the claim that a loop which sometimes runs many times runs few times in total, and the only honest evidence for it is the total. The lab counts every inner-loop iteration while building fail[]. On aabaaab it reports 2 against a bound of 2m = 14; across all five patterns the kit ships, the largest total is also 2. The bound is correct and the measurements are nowhere near it, and both of those facts need saying.

Open the interactive lesson Practice

the inner loop lowers k; the outer loop raises it by at most 1 per character so total falls ≤ total rises ≤ m − 1, and inner iterations ≤ 2m overall aabaaab: fail = 0, 1, 0, 1, 2, 2, 3 inner iterations = 2 bound 14 the chain from the whole pattern: 7 -> 3 -> 0 on the text: KMP 19 comparisons, naive 42, bound 2n = 36 across the five shipped patterns the largest inner total is 2, never 14

A loop inside a loop, and the argument that it is still linear

Core ideas

What this lesson establishes

The hard idea is the potential argument: nothing bounds one step, and the sum is bounded anyway. The other two are what the count is and why it sits so far below.

No bound on one step, and a bound on the sum

While building fail[] at character i, the inner loop follows the fallback chain as far as it has to: on aaaaab that is several steps at one character, and there is no useful ceiling on a single character's work other than m. The claim is about the sum over the whole construction, and the argument never looks at an individual step. k rises by at most 1 per character of the pattern, so across the whole loop it rises by at most m − 1; every inner iteration strictly lowers k, and k never goes below 0; so the number of inner iterations is at most the total rise, m − 1. Adding the one comparison per character gives the 2m the panel prints.

The measured total is the only honest evidence for an amortised claim

A page can say “amortised O(m)” and show a pattern where the inner loop runs twice at one character, which demonstrates nothing in either direction. What settles it is the sum: on aabaaab the construction performs 2 inner iterations in total, on ababaca 2, on abcabcabd 2, and on aaaaa and abcdefg none at all. Every one of those is far under 2m, and it is the total rather than the worst character that the bound is about.

Far under the bound is the normal case, and does not make the bound loose

2 against 14 is a factor of seven, and the bound cannot be improved to a constant: patterns exist for which the inner loop runs a number of times proportional to m. What the gap shows is that the amortised argument is doing its work in the worst case and is invisible in the ordinary one — which is precisely why the argument has to be a proof and not a survey of examples.

The material

Counting the loop nobody can bound one step at a time

The construction, the potential argument, the measured totals across every pattern the kit ships, and where the two meet.

The construction walks i from 1 to m − 1 holding k, the length of the current border. If p[i] equals p[k] the border extends and k rises by 1. If not, k falls to fail[k] and the test is repeated — that repetition is the inner loop, and it is the only part of the algorithm whose cost is not one per character.

Theorem · The inner loop runs at most m − 1 times in total

Over the whole construction of fail[] for a pattern of length m, the number of inner-loop iterations is at most m − 1, so the total work is at most 2m − 1 operations and the construction is O(m).

Take k as a potential. It starts at 0 and is never negative, because the inner loop stops at 0 and fail[j] ≥ 0 for every j.

The outer loop runs m − 1 times and each iteration increases k by at most 1, so the total increase over the whole construction is at most m − 1.

Every inner-loop iteration sets k to fail[k], which is strictly less than k because a border of p[0..k−1] is shorter than it. So each inner iteration decreases the potential by at least 1. Since the total decrease cannot exceed the total increase plus the starting value, the number of inner iterations is at most m − 1.

□

The panel prints that total under the name inner-loop iterations and the bound beside it as 2m. The bound it prints is the looser 2m rather than m − 1 because it is counting the outer comparison as well, and because 2m is the form the claim is usually quoted in.

Example · Seven prefixes of aabaaab, and where the chain is followed

The pattern is aabaaab and fail[1..7] comes out 0, 1, 0, 1, 2, 2, 3. The inner loop fires at exactly two places: at the b in position 3, where the border of length 1 cannot be extended and falls to 0, and at position 6, where the border of length 2 cannot be extended by an a and falls to 1 — from which the a does extend it back to 2. One iteration each, two in total, against a bound of 14.

The same count on the other patterns the kit ships

pattern m fail[1..m] inner bound 2m ababaca 7 0 0 1 2 3 0 1 2 14 aaaaa 5 0 1 2 3 4 0 10 abcabcabd 9 0 0 0 1 2 3 4 5 0 2 18 aabaaab 7 0 1 0 1 2 2 3 2 14 abcdefg 7 0 0 0 0 0 0 0 0 14

Two of the five never enter the inner loop at all. aaaaa never needs to, because every character extends the border; abcdefg never needs to, because k is 0 at every step and the loop's guard is k > 0. The three that do enter it enter it twice, and on ababaca and abcabcabd those two iterations both happen at a single character, while on aabaaab they are one at each of two characters.

That distinction is worth holding on to, because it is where an amortised argument earns its keep. A pattern whose chain is followed twice at one character has a step the per-character reasoning cannot bound; a pattern whose chain is followed once at each of two characters does not. Both have the same total, and the total is what the theorem is about.

The construction is not the matching, and both are counted

The failure function costs O(m) and the search over the text costs O(n), and the panel keeps them in separate counters because they are separate claims with separate proofs. On the text aabaaabaaabaabaaab, 18 characters, the search makes 19 comparisons against a bound of 2n = 36 and finds 3 occurrences at offsets 0, 4 and 11. The naive matcher makes 42 on the same input.

So the full accounting for KMP on this input is 2 inner iterations plus the 6 outer comparisons to build the array, and then 19 comparisons to search: under 30 operations where naive matching spends 42 comparisons alone. The preprocessing is cheap here, and on a long text it is negligible — which is the practical reason the failure function is built at all rather than the theoretical one.

Why the search bound is 2n and not n

The search loop has the same shape as the construction: one comparison per text character, plus a fallback loop that lowers k. The same potential argument applies with k rising at most once per text character, so the fallbacks total at most n and the whole search is at most 2n. The factor of two is the fallbacks, and it is the price of never moving the text pointer backwards.

On this text the measured 19 is just over n, so almost all of those comparisons advanced the text pointer and hardly any were fallbacks. On the adversarial input from the previous module KMP made 44 comparisons on 24 characters, which is close to 2n and is the shape the bound was written for.

Interactive

The failure function, built character by character

Every border found twice: in linear time, and by trying every length

Build the array one character at a time and count the fallbacks

The counter marked inner-loop iterations is the total over the whole construction, not the worst single character, and the counter beside it is the proved 2m. Move the slider to walk the construction forward and watch which characters make the border fall rather than rise.

Worked example

The pattern

The text to search

Build up to character1

Pattern length m—

Inner-loop iterations—

The bound 2m—

Longest border of the whole pattern—

Comparisons, KMP on the text—

Comparisons, naive on the text—

The bound 2n—

Matches, and matches by definition—

A BORDER of a string is a proper prefix that is also a suffix. fail[k] is the length of the longest border of the first k characters, and it is the whole of KMP: on a mismatch after k matched characters the pattern slides so that those fail[k] characters line up again, and the text pointer never moves back. The third column is that length found by trying every one of the k − 1 possible lengths and comparing two substrings, which is how you check a linear-time construction.

Method

Reading an amortised claim without believing an example

Find the potential, check it only ever rises slowly, and then add up the falls.

Name the quantity that rises and falls

Here it is k, the current border length. Every amortised argument on this path has one: a potential that the cheap steps raise a little and the expensive steps consume. Naming it is most of the proof.

Bound the total rise, not the individual steps

k rises by at most 1 per character of the pattern, so across the construction it rises by at most m − 1. That single sentence is what makes the falls bounded, and it is a statement about the loop's shape rather than about any pattern.

Count the falls in the lab, on more than one pattern

The counter is a total. Type a pattern with a long repeated block, one with none, and one that is a single letter repeated, and watch the total stay far under 2m on all three while the shape of the array changes completely.

Keep construction and search in separate columns

O(m) to build and O(n) to search are two claims with two proofs, and the lab prints four counters for them rather than one. Adding them into a single figure hides which half a change affected.

Totals, potentials, and what a bound is bounding

Score 0 / 0

Choose the answer you can justify.

Two inner iterations, located exactly

The pattern is aabaaab. The construction runs i from 1 to 6 holding k, the current border length, and writes fail[i + 1] = k after each step.

i p[i] k before inner iterations k after fail[i+1] 1 a 0 0 1 1 2 b 1 1 (1 -> 0) 0 0 3 a 0 0 1 1 4 a 1 0 2 2 5 a 2 1 (2 -> 1) 2 2 6 b 2 0 3 3 fail[1..7] 0 1 0 1 2 2 3 inner iterations, total 2 the bound 2m 14 the fallback chain from 7 7 -> 3 -> 0

Look at row 5. The border is 2, meaning aa is both a prefix and a suffix of aabaa; the next character of the text-side is a and the next character of the border-side is b, so the border cannot extend and falls to fail[2] = 1. From length 1 the a does extend, so k ends at 2 — the same value it started with, after one iteration of the inner loop. Work was done and the potential did not change, which is exactly the case per-step reasoning cannot handle.

For a faded rehearsal, run the same six rows for ababaca. The supplied first move: the first three characters give k values 0, 1, 2 with no inner iterations at all. Find the single character where the chain is followed twice, give the total, and check it against the lab by switching the preset.

Then predict, before looking, what the total is for aaaaa and why. Say which clause of the inner loop's guard is responsible, and then say what that implies about patterns over a one-letter alphabet in general.

Common mistakes

Arguing the bound from the worst single character“The inner loop can run m times, so the construction is O(m^2)” is the error the potential argument exists to answer. One character really can cost m, and the sum over all characters still cannot exceed m − 1, because the expensive character has consumed rises that earlier cheap characters paid for.

Reading a small measured total as a tighter bound2 against 14 on five different patterns is five measurements, and the bound is about all patterns. Patterns exist whose construction really does perform a number of fallbacks proportional to m; none of them is among the presets, which is a fact about the presets.

Merging the construction cost into the search costThey are O(m) and O(n) and they are proved separately; the panel keeps four counters rather than one for that reason. A change to the fallback rule moves the first pair and leaves the second alone, and a single combined number would hide which.

Check your understanding

✓

Finish when you can state the potential, prove the total bound from it, and read the measured total as evidence rather than as the theorem.

You should be able to identify k as the quantity that rises slowly and falls in the inner loop, bound the total rise at m − 1, conclude the same for the falls, locate each inner iteration in a hand construction, and say why a measured total of 2 neither establishes nor threatens the bound of 2m.

Note: Both of the preprocessing costs on this page are O(m) and both buy something at search time. “The Matcher as a Machine” asks what happens if you are willing to spend more than O(m) up front: writing out every transition for every character of the alphabet removes the fallback loop entirely and makes the search exactly one step per character, at a table cost of (m + 1) times the alphabet size.