In KMP string matching, what does the failure (prefix) function table store?
answer
- It is built from the pattern only
- Think prefixes that are also suffixes
- The word 'proper' matters here
- Answers: how much can I keep?
- Longest border of each pattern prefix
basics
~20 sFor each prefix of the pattern, the failure function stores the length of the longest proper prefix of that prefix which is also a suffix of it. It is derived from the pattern alone and says nothing about the text.
solid answer
~50 sThe failure function (also called the prefix function or border array) is an array of the same length as the pattern. Entry `i` holds the length of the longest **proper** prefix of `pattern[0..i]` that is also a suffix of `pattern[0..i]` — "proper" meaning it may not be the whole thing. For the self-repetitive pattern `abcabcab` the entries run `0 0 0 1 2 3 4 5`: by the last position, `abcab` is both a prefix and a suffix, so five matched characters can be kept after a mismatch. It is computed once from the pattern in O(m) time and O(m) space, before a single text character is read, and it never references the text. Its job is to answer "how much of what I already matched is still valid?", not "where does the pattern occur?".
go deeper
Be ready to state the definition cleanly and fill in the table for a short repetitive pattern on a whiteboard. Say out loud that it comes from the pattern alone, before any text is read.
Explain why the longest border is the right quantity: after a mismatch, only a prefix that matches a suffix of the already-matched region can still align. Know the O(m) build cost and the fallback chain.
Show you know the conventions differ (leading sentinel versus zero-based border lengths) and pin one down before reasoning aloud, since off-by-one table bugs are the classic way a hand-rolled matcher silently misses occurrences.
Be able to argue whether a hand-maintained table belongs in your codebase at all, versus a well-tested library scan, and when the periodicity fact it exposes is worth more to you than the search itself.
## The table, precisely KMP searches for a pattern `P` of length `m` inside a text `T` of length `n`. Before it reads one character of the text it builds a small table out of the pattern alone. That table goes by three names — failure function, prefix function, border array — and they all mean the same thing. Two definitions first. A **prefix** of a string is any starting slice of it; a **suffix** is any ending slice. A prefix or suffix is **proper** when it is not the entire string. A **border** of a string is a slice that is simultaneously a proper prefix and a proper suffix of it. The table entry is then: `fail[i]` = the length of the longest border of `P[0..i]`. Without the word *proper*, every string would trivially answer "myself", and the table would be useless. ## Worked on a self-repetitive motif Take the periodic-looking pattern `abcabcab`: | i | P[0..i] | longest border | fail[i] | |---|---------|----------------|---------| | 0 | a | (none) | 0 | | 1 | ab | (none) | 0 | | 2 | abc | (none) | 0 | | 3 | abca | a | 1 | | 4 | abcab | ab | 2 | | 5 | abcabc | abc | 3 | | 6 | abcabca | abca | 4 | | 7 | abcabcab | abcab | 5 | Notice the values climbing in step with the repetition. That is exactly the structure KMP exploits: a pattern that repeats itself internally is a pattern where a mismatch deep inside can be resumed a long way in rather than restarted. ## Why this is the useful quantity Suppose the scan has matched `j` characters and the next comparison fails. What is known is that the text ends, right there, with the string `P[0..j-1]`. Any alignment of the pattern that could still succeed must place a prefix of the pattern over a suffix of that already-matched region — otherwise it disagrees with characters already read. The longest such prefix has length `fail[j-1]`. So the algorithm sets `j = fail[j-1]` and tries again from there, without touching the text position. If that also fails, applying the table again gives the next-longest border, and so on down to zero. So the table answers exactly one question: **how much of what I have already matched can I keep?** ## What it does not store - **Not text positions.** The table is built before the text is seen and is identical for every text you search. "It records where the pattern occurred" is the single most common wrong answer. - **Not occurrence counts.** It measures a length, not a frequency. - **Not a skip distance keyed by character.** Skip-based algorithms such as Boyer-Moore-Horspool also precompute from the pattern, but their tables are indexed by alphabet symbol and answer a different question: *how far do I shift the pattern given the character that just failed?* KMP's table is indexed by matched length and answers *how much do I retain?* Confusing the two leads people to claim KMP skips text characters, which it does not. - **Not something recomputed during the scan.** It is built once per pattern. Reuse it across as many texts as you like. ## Building it The construction is the matching loop pointed at the pattern itself: slide the pattern along its own tail, using the entries already computed to fall back on mismatch. The build is O(m) time and O(m) space, and it is the whole of the `+ m` in KMP's O(n + m) bound. ## A bonus property worth knowing `m - fail[m-1]` is the smallest period of the pattern. For `abcabcab` that is `8 - 5 = 3`, and indeed the motif is `abc` repeated and then cut short. When that period divides `m` exactly, the pattern is a whole number of repetitions of a shorter block. This is why the same table shows up in problems about string periodicity and repeated blocks, not just in searching — a good thing to be able to mention when an interviewer asks whether the table is good for anything else. ## Boundary details people trip on `fail[0]` is always 0: a single character has no proper prefix. Some presentations shift the array by one and store a leading sentinel of -1; the content is the same, only the indexing convention differs, so say which convention you are using before you start writing values on a whiteboard. And when a full match is reported, the scan continues by setting `j = fail[m-1]` — which is how overlapping occurrences are found without any rewinding.
- Why does the definition insist on a proper prefix?Without it, every prefix's longest prefix-that-is-also-a-suffix would be the whole prefix itself, so every entry would just be its own index plus one. The table would carry no information and the fallback step would loop forever, never shortening the matched region.
- Does the table depend on the alphabet or on the text being searched?Neither. It is a function of the pattern's own self-overlap, so the same pattern yields the same table whether you scan natural-language text, binary data, or nothing at all. That is precisely why it can be computed once and reused across every search with that pattern.
- What does the last entry tell you about the pattern itself?Pattern length minus the last entry is the pattern's smallest period. If that period divides the pattern length exactly, the pattern is a shorter block repeated a whole number of times; otherwise it is a repetition cut short, like a periodic motif truncated mid-cycle.
It is a bookmark rule written before you start reading: if you lose your place at word j, the table tells you how many words of what you just read still count toward the phrase you are hunting.
saying these in an interview costs you the question
- Says the table records where the pattern occurs in the text
- Thinks the table is built while scanning the text
- Drops 'proper' and gives each entry as its own length
- Calls it a per-character skip distance like Boyer-Moore's
- Claims a new table is needed for each text searched