Lesson · Strings and Pattern Matching · Preprocessing the pattern

The Matcher as a Machine

KMP still compares characters and still falls back. Precompute, for every state and every letter of the alphabet, how much of the pattern would then be matched, and both disappear: the run is n lookups whatever the text is. The cost is a table of (m + 1) times sigma cells. On the lab's opening pattern that is 18 cells against a run of 19 steps, and widening the alphabet grows the table while the run does not move.

Open the interactive lesson Practice

one state per number of pattern characters matched: 0 to m delta(state, c) = the longest prefix of p that is a suffix of p[0..state−1] + c table size (m + 1) × sigma; ababc over a, b, c is 6 × 3 = 18 cells the run is exactly n steps, 19 here, with no comparison anywhere state 4 on an a goes to 3, not to 0: the border is compiled into the table KMP made 21 comparisons on the same text; the automaton made 0

A table built once, and a run whose cost does not depend on the text

Core ideas

What this lesson establishes

The hard idea is that the table is the failure function unrolled. The other two are what the run costs and what the table costs, and they move in opposite directions.

A state is a matched length, and the transition is a longest-suffix question

The machine has m + 1 states, state j meaning that the last j characters read are exactly p[0..j−1] and no longer prefix of the pattern ends here. The transition from state j on character c is the length of the longest prefix of the pattern that is a suffix of p[0..j−1] followed by c. On ababc that makes delta(4, a) = 3, because ababa ends in aba which is a prefix of the pattern; the border is not consulted at run time because it has already been compiled into the cell.

The run is n steps, independent of the text

Reading a character means one array lookup and one assignment. There is no comparison to succeed or fail and no fallback loop, so the work is the same on every text of the same length: the panel reports 19 steps for 19 characters, and it reports n steps for n characters on anything you type. This is the only matcher on the course whose count does not depend on the characters at all, which is worth noticing precisely because every other page here is about how much it does depend on them.

The table is the price, and it is charged per letter of the alphabet

(m + 1) times sigma cells have to be written before a single character of the text is read. On ababc over three letters that is 18; on the over the thirteen distinct characters of its text it is 52, for a pattern less than half as long. KMP stores m numbers instead and pays a fallback loop at run time. That is the whole trade, and which side of it wins depends on the alphabet and on how long the text is — the panel prints table cells per text character so the comparison is a number rather than an intuition.

The material

Compiling the pattern into a table, and reading the text once

The construction, the proof that one step per character suffices, and the two costs that move in opposite directions.

Definition · The string-matching automaton

For a pattern p of length m over an alphabet A, the matching automaton has states 0, 1, ..., m and a transition function delta defined by: delta(j, c) is the length of the longest prefix of p that is a suffix of the string p[0..j−1] followed by c. State m is accepting. The machine starts in state 0 and reads the text one character at a time.

The definition is a statement about strings and mentions no algorithm, which is why the table can be built by the obvious method — for each state and each character, form the string and try every prefix length downwards — and why the lab does exactly that, writing (m + 1) times sigma cells and counting each write.

Theorem · The state after reading a prefix of the text is the longest match ending there

If the machine is started in state 0 and fed t[0..i], it ends in the state equal to the length of the longest prefix of p that is a suffix of t[0..i]. Consequently it is in state m exactly when an occurrence of p ends at position i.

By induction on i. Before anything is read the longest prefix of p that is a suffix of the empty string is the empty prefix, of length 0, and the machine is in state 0.

Suppose after t[0..i−1] the machine is in state j, the length of the longest prefix of p that is a suffix of t[0..i−1]. Any prefix of p that is a suffix of t[0..i] and has length at least 1 has its last character equal to t[i] and its first part a suffix of t[0..i−1] that is also a prefix of p, hence of length at most j.

So the candidates are exactly the prefixes of p that are suffixes of p[0..j−1] followed by t[i], and the longest of those is delta(j, t[i]) by definition. The machine moves there, which completes the induction. State m then means the whole pattern is a suffix of what has been read, which is an occurrence ending at i.

□

Example · Eighteen cells, and the transition that carries the border

The lab opens on the pattern ababc over the alphabet {a, b, c}, so there are 6 states and 18 cells. The row for state 4 — abab matched — reads a → 3, b → 0, c → 5. The first of those is the interesting one: reading an a after abab gives ababa, whose longest suffix that is a prefix of the pattern is aba, so the machine drops to 3 rather than restarting at 0 or advancing to 5. Everything the failure function would have computed at run time is sitting in that cell.

The run over abababcababcabababc takes exactly 19 steps for 19 characters and finds 3 occurrences, at offsets 2, 7 and 14. The counter for character comparisons does not exist on this page, because the algorithm makes none.

The trade, in two numbers that move in opposite directions

KMP makes 21 comparisons on that same text and stores 5 numbers. The automaton makes 0 comparisons, takes 19 steps, and stores 18. Neither is dominant: the automaton is ahead on the run and behind on the setup, and which matters depends on how many texts one table will be used for.

preset pattern m sigma states cells n run KMP cells/char ababc ababc 5 3 6 18 19 19 21 18/19 aaab aaab 4 2 5 10 15 15 18 2/3 binary 10110 5 2 6 12 36 36 43 1/3 distinct abcd 4 4 5 20 14 14 16 10/7 wide the 3 13 4 52 38 38 40 26/19

Read the last two columns together. The run column is the text length in every row, with no exceptions and no dependence on the characters. The cells column moves by a factor of five across the same rows, and it moves with sigma rather than with m: the is the shortest pattern in the table and has the largest table, because its text uses thirteen distinct characters.

The last column is cells per text character, and it is the number that decides. Below 1 the table is cheaper than the text it will read; above 1 it is not, and a single search would have been better served by KMP. The binary preset sits at 1/3 and the wide one at 26/19, on the same algorithm.

Why KMP is what actually gets used

The automaton's table is (m + 1) times sigma. For byte data that is 256 cells per state, and for Unicode text it is not a table one writes out at all. KMP stores m integers regardless of the alphabet and pays for it with a fallback loop whose total cost is bounded by the same potential argument that bounds the construction.

So the automaton is the clearer explanation and the worse implementation, and it is worth building once for exactly that reason: delta(j, c) is what fail[] is compressing, and a reader who has seen the table knows what the fallback chain is walking through.

Interactive

The matcher as a machine, and what the table costs

(m + 1) times sigma cells built once, then exactly one step per character

Read the whole transition table, then watch the machine walk the text

Every cell is the number of pattern characters that would be matched after reading that character in that state, and the row highlighted is where the machine stands at the position the slider picks. Widen the alphabet by typing into the text box and watch the table grow while the step count stays exactly n.

Worked example

The pattern

The text

Show the state after character1

States—

Alphabet size—

Table cells—

Writes to build it—

Steps to run it—

Comparisons, KMP—

Cells per text character—

Matches, and matches by definition—

The automaton has one state per number of pattern characters matched so far, and a transition for every character of the alphabet, so the table is (m + 1) times sigma cells. Running it is then exactly one array lookup per text character with no comparison and no back-up at all — the run is n steps whatever the text is. That is the trade the lesson is about, and both halves of it are numbers above: widen the alphabet and the table grows while the run does not move.

Method

Building a table, and pricing it against the text

Fill one row by hand before reading the panel's, then compare the two costs in the same unit.

Fill one row from the definition

For state j and character c, write down p[0..j−1] followed by c and then ask for the longest prefix of the pattern that is a suffix of it. Trying lengths downwards from min(m, j + 1) gets there in a few steps and needs no algorithm.

Check the accepting row and the zero row first

State m's row is the same as the row for the pattern's longest border, because after a full match the machine is exactly as far along as that border leaves it. State 0's row is 1 for p[0] and 0 everywhere else, always.

Count the cells before counting the steps

(m + 1) times sigma is fixed by the pattern and the alphabet and is paid whether or not the text is ever read. A table of 52 cells for a text of 38 characters is a loss before the search begins.

Widen the alphabet, not the pattern, to see the cost move

Adding one distinct character to the text adds m + 1 cells and adds nothing to the run. That asymmetry is the whole argument for KMP, and it is visible in one keystroke.

States, cells, and steps

Score 0 / 0

Choose the answer you can justify.

The eighteen cells of ababc, and one walk across the text

The pattern is ababc and the alphabet of the text and pattern together is {a, b, c}, so the machine has 6 states and the table has 18 cells. Each entry is the length of the longest prefix of ababc that is a suffix of the state's string followed by the column's character.

state matched a b c why the a column is what it is 0 - 1 0 0 'a' is a prefix of length 1 1 a 1 2 0 'aa' ends in 'a' 2 ab 3 0 0 'aba' is a prefix of length 3 3 aba 1 4 0 'abaa' ends in 'a' 4 abab 3 0 5 'ababa' ends in 'aba' 5 ababc 1 0 0 'ababca' ends in 'a' cells (m + 1) x sigma = 6 x 3 = 18 writes to build it = 18 text abababcababcabababc, n = 19 steps to run it = 19 comparisons made = 0 KMP on the same text = 21 matches at offsets = 2, 7, 14

The cell to argue with is state 4 on an a. The naive intuition says a mismatch throws everything away and the machine restarts at state 1, having just read an a. The right answer is 3, because ababa ends in aba and aba is a prefix of the pattern — two characters of progress that the restart would have discarded. The same two characters are what fail[4] = 2 encodes in the failure function.

For a faded rehearsal, build the table for aaab over {a, b}. The supplied first move is the a column: from states 0, 1 and 2 it climbs 1, 2, 3, and from state 3 it stays at 3 rather than reaching 4, because aaaa is not a prefix of aaab but aaa is. Fill the b column, give the cell count, and check against the lab.

Then do the pricing exercise. Keep the pattern the and add a single new distinct character to the text — a digit will do. Say by how many cells the table grows, by how many steps the run grows, and what happens to cells per text character. Then say which of those three you could have predicted without the lab.

Common mistakes

Thinking a mismatch sends the machine to state 0It sends it to whatever the cell says, which is often neither 0 nor the state before. delta(4, a) = 3 on ababc is the example on screen: the machine loses one character of progress, not four. Every cell of the table is a separate longest-suffix computation and none of them is a restart rule.

Counting the table as part of the search costThe table is built once from the pattern and is independent of the text, so a program searching a thousand documents for one pattern pays 18 cells once and 19 steps a thousand times. The cells-per-character figure on the panel is for a single search, and it is the pessimistic reading.

Treating sigma as a property of the patternThe lab builds the table over the characters of the text and pattern together, because a transition is needed for every character the machine might read. Pasting a text with an accented letter in it widens every row, and the pattern has not changed at all.

Check your understanding

✓

Finish when you can fill a transition row from the definition and price the table against the text in one unit.

You should be able to state what state j means, compute delta(j, c) as a longest-suffix question, prove that the machine's state is the longest match ending at the current position, give the cell count as (m + 1) times sigma, and say why the run is n steps on every text.

Note: That closes the pattern-preprocessing module: three matchers that all read every character of the text, differing only in what they remember. The next module gives that up. “Shifting by More Than One” skips over characters without reading them at all, which buys a large saving on ordinary text and buys no guarantee whatsoever — its worst case is the same m(n − m + 1) the naive matcher has.