The problem
A search can compare a pattern with the same text positions repeatedly. A mismatch does not necessarily make all previously matched information useless: a suffix of the matched part may also be a prefix of the pattern. The prefix function records exactly those possible fallbacks.
Let be a nonempty sequence of length and a sequence of length . Positions are zero-based. We report every start position at which occurs in , including overlapping occurrences. Symbols may be characters, integers or other tokens; their equality test must be a stable equivalence relation and is counted as one operation. We also assume constant-time indexed access to the pattern and prefix table, and constant-time sequential access to each text symbol. A convention for the empty pattern is deliberately outside this unit.
Borders and the prefix table
Definition 6.1.1
(Border and prefix function)
A border of a sequence is a proper prefix that is also a suffix; the empty sequence is allowed, and proper means shorter than the whole sequence. For each , let be the length of the longest border of . Thus , and always .
Lemma 6.1.2
(Prefix fallback)
If a prefix of length matches a suffix of the text processed so far and the next symbols disagree, every shorter prefix that could match the already processed text suffix before comparing that next symbol is a border of that length- prefix. The longest possible fallback has length when . Repeating this step considers shorter candidates without rereading the text.
Proof
(Every viable fallback is a border, and the borders form a chain)
Suppose a shorter prefix of length also matches the same processed-text suffix. The last symbols of the matched length- prefix are therefore the first pattern symbols: is a border length. The longest such border has length . Any still shorter border is also a border of that longest border, so applying the same rule repeatedly visits every possible remaining border length, ending at zero. A disagreement excludes the candidate just tested; no viable candidate is discarded.
Proof X-ray
Why the border chain is complete
The key move is to compare two prefixes only through the text: both equal the same suffix of the processed text, so the shorter is the end of the longer. This is the one place where equality must behave as an equivalence relation. With the tolerance relation "differ by at most one" on integers, and but , so two prefixes could both match the text without the shorter being a border of the longer, and the chain would miss candidates.
The chain is complete because a border of a border is again a border of the original sequence. The process closes at length zero, which is always a border. Dropping a candidate only after a failed comparison is safe, since a failed comparison means that candidate cannot be extended by the next text symbol.
Computing the table follows the same chain on the pattern itself.
Theorem 6.1.3
(Prefix table construction)
For start with . While and , replace by . If , increase by one. Then . Each entry refers only to earlier entries.
Proof
(A border of comes from a border of )
Let be the length of a border of . Dropping the last symbol of the prefix and of the suffix leaves a border of of length , and the dropped symbols agree: . Conversely, a border length of with gives a border of length of , which is proper because .
So is the largest border length of with , if one exists. Because a border of a border is again a border, the border lengths of in decreasing order are , and the loop tests exactly these in order. It stops at the first with , giving . If the chain ends at with , no border of positive length exists and . When the equality test still decides whether the first symbol starts a border.
Worked example 6.1.4
(Building the table for ababaca and abaab)
For the entries are : the prefix has longest border , and the symbol continues no border, so the entry drops to .
Now take . We have and since , and . For start with ; , so fall back to , where and so . For start with ; now , so . The table is , and is indeed the longest border of .
Scanning without losing overlaps
Definition 6.1.5
(Scan state)
After processing a prefix of the text, is the length of the longest proper pattern prefix that is a suffix of the processed text. A complete occurrence ending at the current symbol is detected when a pattern prefix of length matches, and is then reported before is reset.
Keep , the length of a pattern prefix matching a suffix of the text already processed. Before reading a text symbol, . For each symbol , while and , set . If , increment . If it becomes , report the start position and reset . The reset keeps the longest proper border of the matched pattern, so a later occurrence may overlap the one just reported.
Theorem 6.1.6
(The scan reports exactly the occurrences)
The scan above reports every start position at which occurs in , in increasing order, and no other position. After each symbol and any report, is the length of the longest proper pattern prefix that is a suffix of the processed text.
Proof
(Induction on the number of processed symbols)
Before any symbol, and the claim holds. Suppose it holds before reading . A pattern prefix that matches a suffix of the text including is a pattern prefix of length whose first symbols match a suffix of the earlier text and whose last symbol equals . By hypothesis the candidates are the border chain starting at : the longest is , and the next ones are , , and so on, by the fallback lemma. The loop tests them from longest to shortest and stops at the first with , so it finds the longest extension; if none exists, is zero after the test. If becomes , the suffix is a complete occurrence ending at the current position, so its start is reported. Its longest proper border is exactly the state needed for the next symbol. Conversely, a full-length prefix matching a suffix of the text ending at the current symbol is an extension of length , which is the longest possible, so the loop reaches exactly at occurrences. Hence no occurrence is missed and no false one is reported.
Concept lensStructural
The scan as a finite automaton
The state is a state of a deterministic automaton. On a symbol it moves to the length of the longest pattern prefix, the whole pattern allowed, that is a suffix of , which is what the fallback loop computes, and a complete match is the event that this length would be . The prefix table stores the transition rows implicitly, as a chain of fallbacks, instead of rows over the whole alphabet.
Worked example 6.1.7
(A mismatch that reuses a prefix)
For , the table is . Search . After five text symbols, ; the next symbol is , while . Fall back to , where the same text symbol matches. Continuing finds the pattern at zero-based position . The text symbol causing the mismatch was not read a second time from the input.
Worked example 6.1.8
(Edge cases: all-equal symbols and a text shorter than the pattern)
Take , with , and . Reading the first symbol gives , the second gives , so report position and reset to . Each later symbol again raises to and reports positions and . The overlapping occurrences are .
If is empty or shorter than , no symbol sequence can reach , and the scan reports nothing in steps; the table is still built in .
Counterexample mode
Resetting to zero can lose a match
In , the pattern occurs at positions and . After the first match, retains the final as the start of the next candidate. Resetting to zero instead loses the overlapping occurrence: the next symbols leave and the scan ends without reporting position .
Why the total work is linear
Theorem 6.1.9
(Linear running time)
With constant-cost equality tests, building the table takes time and scanning the text takes time, so the total work is . The table uses space.
Proof
(Amortized by the potential q)
During the text scan each symbol can increase at most once. Every fallback strictly decreases , and cannot become negative. Therefore the total number of fallback steps is at most the total number of increases, hence ; the reset after a report is one more decrease. The prefix-table construction has the same argument with the value and at most one increase per pattern position, so it takes . The table has entries.
Reporting positions takes output space if they are stored; emitting them one at a time does not require that storage. This bound counts symbol equality as constant-cost. If tokens are long strings or structured objects, their comparison cost must be included separately. The algorithm gives exact equality matches, not approximate or semantic similarity.
Common mistakes
Common mistake
(Falling back to the table entry at q instead of at q minus one)
The fallback uses , the border of the matched prefix of length , not . In the search of for the mismatch occurs at . The correct value is . Using drops to , the remaining symbols never rebuild the prefix, and the occurrence at position is missed.
Common mistake
(Counting the whole prefix as a border)
A border must be a proper prefix. If the table allowed the whole prefix, then for it would read . After a match the reset would leave equal to the pattern length, so the next comparison would read outside the pattern, and each fallback would never decrease .
Exercises
Quick check
(Compute for .)
Find the longest border of each prefix , , , .
Solution · Answer
The table is : each prefix's longest proper border removes one trailing symbol.
Quick check
(Report all zero-based occurrences of in , and give the reset after the first match.)
Use for this pattern.
Solution · Answer
Positions are ; after the first match the reset is .
Quick check
(What happens to a text symbol when and it differs from ?)
Ask which nonempty pattern prefix could end at that symbol.
Solution · Answer
No nonempty prefix can end at that symbol, so stays zero and the scan advances to the next symbol.
Quick check
(Why does one long chain of fallbacks not make the complete scan quadratic?)
Think of as a quantity that can be spent only after it has been earned.
Solution · Answer
Each fallback decreases a nonnegative . Across the whole scan, decreases are bounded by earlier increases, of which there is at most one per text symbol.