The KMP unit matches a pattern deterministically by following prefix information. Another strategy compares short numerical summaries of equal-length strings. These fingerprints can be updated efficiently as a window moves, but equal fingerprints are only candidates for equality.
A polynomial for a string
Let be prime, and encode every symbol of a finite alphabet injectively as an element of . Fix a pattern of length and a text of length before choosing the random seed. Choose uniformly from the whole field, independently of those strings.
Definition 6.3.1
(Polynomial fingerprint)
For an encoded length- string and a base , the fingerprint is
The constant power is , including when .
Equal strings always have equal hashes. For distinct strings , injectivity ensures that their difference polynomial is nonzero and has degree at most .
Theorem 6.3.2
(Collision bound for two strings)
Let be fixed encoded strings of length and let be uniform on . Then
Proof
(Collisions are roots of a nonzero polynomial)
Put . Since the encoding is injective and , some coefficient is nonzero, so is nonzero of degree at most . A collision means exactly .
A nonzero polynomial of degree over a field has at most distinct roots: each root supplies a linear factor, and the product of distinct root factors divides the polynomial. Hence at most of the equally likely values of cause a collision, which gives the bound. For , the nonzero difference is constant and the collision probability is zero. If the degree bound is at least , the displayed probability bound can be uninformative; the proof is still valid.
Proof X-ray
A root count gives a collision bound
The one idea is to turn a probability statement into a root count. Fixing first and drawing afterwards makes a fixed polynomial, and a collision is just a root of among equally likely values.
Each hypothesis is used once. Injectivity of the encoding makes nonzero, so it has finitely many roots. The field property gives the root bound: over the ring the degree-two polynomial has four roots , so the count fails without a field. Uniform independent of the strings turns the root count into a probability. A non-injective encoding can make zero for different symbols, and then every collides.
The next statement covers every window of the text at once.
Theorem 6.3.3
(Collision bound over all windows)
For the fixed windows of , the probability that any window unequal to has the same fingerprint as is at most .
Proof
(Union bound with a shared seed)
Each unequal window collides with with probability at most by the previous theorem. The probability that at least one of at most events occurs is at most the sum of their probabilities, which is the stated bound. All windows use the same seed, so their collision events may be dependent; the union bound does not require independence.
Choosing the strings after seeing is a different adversarial model and is not covered by this fixed-input guarantee.
Moving the window
Let the current window start at position , and write for the encoded text symbol at position . With zero-based positions and , let .
Theorem 6.3.4
(Rolling update)
With as above,
The identity needs no modular division and holds for every , including , and for .
Proof
(Remove the top term, shift, append)
By definition . Subtracting removes the term , leaving . Multiplying by and substituting gives . The missing term of , with , is , which is added. For the sum is empty and the formula reads .
Worked example 6.3.5
(One rolling step in the small field)
Take , , , and , so . The first hash is . Then and
Direct computation gives , so the update agrees with the definition.
Worked example 6.3.6
(Edge case: base zero)
With and , every term except the last vanishes, so is just the final symbol. For the windows have hashes and . The rolling formula still works: and . Such a base makes any two windows with the same last symbol collide, so it is a bad draw. It occurs with probability , consistent with the collision bound.
A collision in a small field
Worked example 6.3.7
(Two distinct windows with the same hash)
Use , encode as , and take pattern and text . The windows are and . For a base ,
They collide exactly when , that is . At that base both hashes are , although ; the second window really matches. Over uniform , this unequal pair collides with probability , matching the degree-one bound.
Counterexample mode
A hash match is not a proof of a string match
At , returning every hash-matching window would incorrectly report the first window of bac as an ac occurrence. Directly compare the symbols of each candidate to remove false positives. This makes the output exact, while the hash alone has a one-sided error: a true matching window never has a different hash under the stated exact field arithmetic.
Work and guarantees
Computing the pattern and first-window hashes and takes field operations; each subsequent window takes more. Assuming constant-time access to the outgoing and incoming encoded symbols, scanning takes field operations. A streaming implementation can retain the last symbols in a circular buffer. Field-operation bit costs depend on and its arithmetic implementation.
Without verification, report hash matches as candidates and use the fixed-input probability bound above. If each hash match is checked symbol by symbol, correctness is deterministic, but up to checks can each cost , including true matches; worst-case work becomes . This does not replace KMP's deterministic linear-time guarantee. Exact random-field sampling and arithmetic are assumptions, not a claim about a particular machine implementation.
Common mistakes
Common mistake
(Removing the outgoing symbol with the wrong power)
The outgoing symbol carries , not , because the window has symbols and its first has exponent . In the example with , , and , using gives , whereas the correct fingerprint of is .
Common mistake
(Fixing the base in advance)
The bound is over a random drawn independently of the strings. If the base is a published constant, a text can be built to collide with the pattern. With and the fixed base , the pattern and the window always collide, as computed above, however large the text is. A draw made after the input is chosen restores the guarantee.
Exercises
Quick check
(For the example and , compute the hashes of and modulo .)
Use and .
Solution · Answer
and . The hashes differ, so at this pair does not collide.
Quick check
(What is the collision probability for two different one-symbol strings under an injective encoding?)
With , what is the fingerprint?
Solution · Answer
Zero. For the fingerprint is the symbol itself, , and injectivity makes different symbols differ whatever is. This matches the bound .
Quick check
(If and , which symbol determines the hash?)
Which power of is not zero when ?
Solution · Answer
The final symbol, since only survives, so . The rolling formula still applies, as the base-zero example shows.
Quick check
(Why can a union bound be used although all windows share one seed?)
What does the union bound assume about the events?
Solution · Answer
The union bound holds for arbitrary events and requires no independence among them. The shared seed makes the collision events dependent, but the probability that at least one occurs is still at most the sum of the individual probabilities.