Lesson · Strings and Pattern Matching · Preprocessing the pattern

Borders, and the Failure Function Built

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 entire content of Knuth–Morris–Pratt: after a mismatch the pattern slides so that fail[k] characters still line up and the text pointer never moves back. The lab builds the array in linear time and, in the same table, finds every border by trying every length.

Open the interactive lesson Practice

border of s: a proper prefix of s that is also a suffix of s fail[k] = length of the longest border of the first k characters ababaca: fail = 0, 0, 1, 2, 3, 0, 1 on prefixes of length 1 to 7 the fallback chain from the whole pattern: 7 -> 1 -> 0 on a mismatch after k matched, retry at fail[k]; i never decreases measured: KMP 34 comparisons, naive 61, on the same 29-character text

One array, computed two ways, and what it is for

Core ideas

What this lesson establishes

The hard idea is the border itself. The other two are the slide it licenses and the reason the fast construction has to be checked against the slow one.

A border is a prefix that is also a suffix, and shorter than the whole

For ababa the borders are aba and a, the longest being aba. For abc there are none but the empty string. The word proper matters: the whole string is trivially a prefix and a suffix of itself and is excluded, otherwise every string would have a border of its own length and the definition would carry no information. Borders are what makes a partial match reusable: if the first k characters of the pattern matched and fail[k] = 3, then three characters of the pattern are already aligned at the new position without a single comparison.

The failure function is that length for every prefix at once

fail[k] is the longest border of p[0..k−1], one number for each k from 0 to m. On ababaca the seven values are 0, 0, 1, 2, 3, 0, 1: the prefix abab has border ab of length 2, ababa has aba of length 3, and ababac has none at all because it ends in c. Following the array from m gives the fallback chain 7 → 1 → 0, which is every length at which the pattern can still be aligned after a mismatch at its end.

A linear construction has to be checked against the definition

Computing fail[] in O(m) is a three-line loop whose correctness is not obvious. Computing it by trying every one of the k − 1 candidate lengths and comparing two substrings is obvious and cubic. The lab's table prints both columns for every prefix and reports how many rows disagree; on the presets that number is 0, and a construction that is fast and right is only interesting once the second half has been demonstrated rather than assumed.

The material

Borders, the array, and the slide it licenses

The definition, the two constructions, the theorem that makes the slide safe, and the counts on the text beside it.

Definition · Border

A string b is a border of a string s if b is both a prefix and a suffix of s and b is shorter than s. The empty string is a border of every non-empty string, so the set of borders is never empty and “the longest border” is always defined.

Definition · The failure function

For a pattern p of length m, the failure function is the array fail[0..m] in which fail[k] is the length of the longest border of the prefix p[0..k−1]. By convention fail[0] is treated as before the start and fail[1] = 0, since a single character has only the empty border.

Example · Seven prefixes of ababaca

The prefixes are a, ab, aba, abab, ababa, ababac and ababaca, and their longest borders are the empty string, the empty string, a, ab, aba, the empty string and a. So fail[1..7] is 0, 0, 1, 2, 3, 0, 1. The rise from 0 to 3 across the middle is the pattern's periodicity; the collapse to 0 at ababac is the c, which occurs nowhere else, so no prefix ending in c can be matched by a prefix starting with a.

The lab's table puts that column beside a second one computed from the definition: for each k, try k − 1, then k − 2, down to 1, and stop at the first length where p[0..j−1] equals p[k−j..k−1] as strings. It is O(m^3) and it is obviously right. The panel reports that the two agree on all 7 prefixes.

Theorem · The slide is safe

Suppose the pattern is aligned at text offset i and its first k characters have matched, so t[i..i+k−1] = p[0..k−1], and the comparison at k fails. Then no offset strictly between i and i + k − fail[k] can begin a match, and at offset i + k − fail[k] the first fail[k] characters already agree.

Let j be an offset with i < j < i + k, and suppose a match begins at j. The match's first i + k − j characters lie inside the region already known to equal p[0..k−1], so p[0..i+k−j−1] equals t[j..i+k−1], which equals p[j−i..k−1].

That says p[0..i+k−j−1] is both a prefix of the pattern and a suffix of p[0..k−1], so it is a border of p[0..k−1] of length i + k − j. Since fail[k] is the longest such border, i + k − j ≤ fail[k], which rearranges to j ≥ i + k − fail[k].

So no offset before i + k − fail[k] can start a match, and at that offset the border itself is the fail[k] characters already in place. The matcher therefore sets k to fail[k] and leaves the text pointer where it is.

□

That last clause is the property the previous module leaned on. The text pointer only ever advances, so the number of comparisons that succeed or advance it is at most n; the rest are fallbacks, and the bound 2n follows. The lab prints both, and on the opening text it reports 34 comparisons against a bound of 58.

The fallback chain, and why it is every alignment worth trying

Applying fail repeatedly from m gives 7 → 1 → 0 on this pattern. Each step is the longest border of the one before, and by the theorem above every length in that chain is an alignment at which the pattern could still match while no length outside it can. The chain is short here because ababaca has one short border; on aaaaa it is 5 → 4 → 3 → 2 → 1 → 0, every length there is.

The counts on the text below

The panel searches abababacaba ababacaab ababaca, 29 characters, and finds 3 occurrences at offsets 2, 12 and 22. KMP makes 34 character comparisons and the naive matcher makes 61 on the same input, so KMP is ahead by 27 here. The bound 2n is 58, and the measured 34 sits well under it.

Read those four numbers as four different kinds of statement. 34 is a measurement. 61 is another measurement, of a different algorithm on the same input. 58 is a theorem about KMP on every text of 29 characters. And 27 is the difference between two measurements, which is the one number of the four that does not generalise at all — the sibling lesson “Where the Simple Algorithm Wins” has it at negative 4.

What the second column is protecting against

The linear construction is short enough to look self-evident and subtle enough to be wrong in a way that survives testing: an off-by-one in the fallback gives an array that is correct on most patterns and too small on periodic ones, and a matcher using a too-small fail[] still finds every match, just slowly. The failure mode is invisible in the output and visible only in the count.

So the table compares against the definition on every keystroke, over whatever pattern you type, and prints the number of rows where the two disagree. Type a pattern of your own and watch the count stay at 0; that is the check being exercised rather than merely present.

Interactive

The failure function, built character by character

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

Type a pattern, and watch its borders appear one prefix at a time

The bar chart is one bar per prefix and its height is that prefix's longest border, found by trying every length. The table puts the linear-time fail[k] beside it, row by row, so the fast construction is checked against the definition rather than trusted — and the slider walks the construction forward one character at a time.

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

Finding a border, and then finding all of them

Do one prefix by hand before running anything. The array is the same operation repeated, and the operation is short.

Write the prefix out and fold it

For ababa, try length 4: abab against baba — no. Length 3: aba against aba — yes. Stop at the first success, because you are counting down from the longest.

Build the array left to right, not prefix by prefix

The linear construction extends the previous answer: if p[k] continues the current border it lengthens by 1, and otherwise the border falls back along the chain. Doing each prefix independently is the checking column, not the algorithm.

Read the chain before reading the array

7 → 1 → 0 says more about how the pattern behaves under mismatch than the seven numbers do. It is the complete list of alignments that survive a failure at the end of the pattern.

Check the two columns on your own pattern, not just on the preset

The agreement on ababaca is a fact about ababaca. Type something periodic, something with a repeated block, and something with no repeats at all, and watch the disagreement count stay at 0 on each.

Borders, the array, and the slide

Score 0 / 0

Choose the answer you can justify.

Every border of every prefix of ababaca, by hand

The pattern is ababaca, seven characters, indexed from 1 for the prefix lengths. For each prefix the longest proper border is found by trying lengths downwards and comparing the two substrings as strings.

k prefix candidate lengths tried longest border fail[k] 1 a (none) empty 0 2 ab 1: a vs b no empty 0 3 aba 2: ab vs ba no; 1: a vs a yes a 1 4 abab 3: aba vs bab no; 2: ab vs ab ab 2 5 ababa 4: abab vs baba no; 3: aba=aba aba 3 6 ababac 5,4,3,2,1 all fail on the c empty 0 7 ababaca 6..2 fail; 1: a vs a yes a 1 fail[1..7] 0 0 1 2 3 0 1 linear construction 0 0 1 2 3 0 1 rows where they disagree 0 fallback chain from 7 7 -> 1 -> 0

Row 6 is the one to look at twice. Five candidate lengths are tried and all five fail, for the same reason each time: the prefix ends in c and every candidate suffix must therefore end in c, while every candidate prefix begins with a. A single character occurring once in the pattern collapses the border to nothing.

For a faded rehearsal, do aabaaab the same way. The supplied first move: aa has border a, so fail[2] = 1, and then the b at position 3 takes it straight back to 0. Complete the seven rows, give the fallback chain, and then check them against the lab by switching the preset.

Then try abcabcabd, where the border climbs to 5 before the final d destroys it in one step. Predict fail[8] and fail[9] before running it, and say which single character of the pattern is responsible for the collapse.

Common mistakes

Including the whole string among the bordersEvery string is a prefix and a suffix of itself, so allowing that would make fail[k] = k for every k and the matcher would never advance. The word proper is doing real work in the definition, and dropping it turns the algorithm into an infinite loop rather than into a slower one.

Reading fail[k] as an index rather than a lengthfail[5] = 3 on ababaca means the longest border of the first five characters has length 3, so after a mismatch three characters are already matched and the next comparison is at pattern position 3. Treating it as “go to index 3” happens to give the same answer only because lengths and zero-based next-indices coincide here; on a one-based reading it is off by one everywhere.

Assuming the failure function says something about the textIt is computed from the pattern alone, before the text is looked at. Two texts searched for the same pattern share the identical array, which is why the construction cost O(m) is paid once and why the lab's upper table does not move when you retype the text.

Check your understanding

✓

Finish when you can build the array by hand for a pattern you have not seen and justify the slide it licenses.

You should be able to state what a border is and why proper matters, compute fail[] by trying every length, read the fallback chain off it, prove that no offset between i and i + k − fail[k] can start a match, and say why a too-small array is a performance defect rather than a correctness one.

Note: The construction itself has a claim attached that this page has not tested: that building fail[] costs O(m) rather than O(m^2), even though the fallback loop inside it can run several times for one character. “The Amortised Bound, as a Count” measures those inner iterations directly and puts them beside 2m.