String Matching: KMP, Z, and Rolling Hashes

Substring search becomes subtle when text is repetitive, input streams, one text serves many queries, offsets cross Unicode representations, or a hash is mistaken for proof of equality.

Knuth-Morris-Pratt, the Z algorithm, and rolling hashes all avoid restarting a full comparison at every text position, but they reuse information differently. KMP preprocesses the pattern into fallback links. Z computes how strongly every position matches a common prefix. Rolling hashes summarize fixed-length windows so most unequal candidates can be rejected in constant time, with a collision policy determining whether the result is probabilistic or exact.

The thesis is that matching begins by defining its sequence. Once units, normalization, offsets, empty-pattern behavior, and collision guarantees are explicit, workload shape selects the algorithm. We will derive all three techniques, trace a KMP fallback, and distinguish guarantees from assumptions in tests.

Define the Sequence and the Match Contract #

An exact matcher operates on a sequence of tokens. Those tokens might be bytes, UTF-16 code units, Unicode code points, grapheme clusters, or domain-specific symbols. The algorithm compares tokens for equality; it does not decide what a user perceives as one character.

Let text length be n and pattern length be m in the chosen units. A match at index s means:

for every j from 0 through m - 1. The API must also answer several questions:

• Does it return the first match, every match, or only a boolean?
• Are overlapping matches included? Pattern aba occurs at indices 0 and 2 in ababa.
• What does an empty pattern mean: an error, index 0, or every boundary?
• Are returned offsets measured in bytes, code units, code points, or graphemes?
• Is comparison byte-exact, normalized, locale-aware, or case-insensitive?

Here the contract searches token arrays, rejects an empty pattern, returns overlapping matches, and reports token indices. A wrapper chooses tokenization and converts indices.

The straightforward algorithm compares from every legal start and costs $O((n - m + 1)m)$ in the worst case. Repetitive text repeats nearly identical work at adjacent starts. Native search may still win for tiny inputs; preprocessing matters when repetition, size, or reuse makes redundancy measurable.

Understand What Preprocessing Reuses #

Each algorithm performs linear preprocessing but reuses a different object. KMP builds pattern fallback metadata and consumes text left to right, fitting streams. Z records the prefix-match length at every position of a combined sequence. Rolling hash builds text prefix hashes and powers so fixed windows can be fingerprinted in $O(1)$; equal fingerprints require verification or an explicitly probabilistic contract.

Setup can outweigh direct comparison on tiny inputs. Pattern-only preprocessing amortizes across text chunks, while prefix hashes amortize when one text serves many equal-length queries.

Build KMP Failure Links from Pattern Borders #

A border of a sequence is a proper prefix that is also a suffix. For pattern prefix ending at index i, the KMP prefix value pi[i] is the length of its longest border. For ababaca, the prefix table is:

Suppose j pattern tokens currently match and the next token mismatches. The matched text suffix equals pattern[0..j). Its longest border is another prefix that may still align with that suffix, so KMP sets j = pi[j - 1] and retries the same text token. It never moves the text index backward.

The prefix table uses the same fallback rule:

for each pattern index i after 0:
  matched = pi[i - 1]
  while matched > 0 and pattern[i] != pattern[matched]:
    matched = pi[matched - 1]
  if tokens match: matched += 1
  pi[i] = matched

for each text index i:
  apply the same fallback until text[i] can extend matched
  after m matched tokens, report i + 1 - m and fall back once

Each fallback decreases matched, while successful extensions increase it only linearly across the scan, giving $O(n + m)$ time. The prefix array costs $O(m)$ memory; a stream retains it, matched, and the absolute token position.

A compiled KMP pattern can therefore expose a small state-machine API: feed one token, update matched, and optionally emit a match. Reusing that object avoids rebuilding pi for each chunk. It must not be shared between independent streams unless each stream stores its own matched state; the immutable pattern table is shareable, but scan position is not.

Work Through a KMP Fallback #

Search for pattern ababaca in text zzabababacayy. The first two z tokens mismatch at pattern index 0 and are discarded. Starting at text index 2, KMP matches ababa, so matched = 5 before it reads text index 7.

At index 7 the text token is b, but pattern index 5 contains c. A naive restart would return to candidate start 3 and recompare text. KMP consults pi[4] = 3. The already matched text suffix aba is also the pattern prefix aba, so three tokens remain useful. It sets matched = 3 and retries the same text token b against pattern index 3.

That comparison succeeds. Text indices 8, 9, and 10 then match pattern tokens a, c, and a, completing a match at:

text:       z z a b a b a b a c a y y
index:      0 1 2 3 4 5 6 7 8 9 10
first try:      a b a b a c
                         mismatch
fallback:           a b a b a c a
                    ^ match starts at 4

The border of the five matched tokens implies the alignment at index 4. Candidate starts not represented by a border already contradict the observed text.

After reporting a complete match, the implementation again falls back using the full pattern’s longest border. This is what permits overlapping matches. Resetting matched to zero would miss an occurrence that begins inside the one just reported.

For chunked input, preserve matched and the absolute offset rather than retaining the previous chunk. A decoder or grapheme segmenter must separately preserve carry state when token boundaries cross chunks.

Use the Z Algorithm for Prefix Matches Everywhere #

For a token sequence s, Z[i] is the length of the longest prefix of s that equals the sequence beginning at i. Z[0] is conventionally 0 or the full length; search logic does not need it. A naive computation compares from the prefix at every position and can be quadratic.

The linear Z algorithm maintains a half-open interval [left, right) matching the prefix. Inside it, copy min(right - i, Z[i - left]), then compare beyond the known region. If matching extends, advance the interval. Because right only moves forward, extensions total $O(n)$.

combined = pattern + unique-separator + text
compute Z over combined
for each text-side index i where Z[i] >= pattern length:
  report i - pattern length - 1

The separator must differ from every token; an unproven character such as $ can let a match cross the boundary. Use a unique tagged token, a wider alphabet, or a sentinel-free implementation.

KMP and Z share deterministic linear bounds. KMP is naturally incremental; Z exposes every prefix-match length. Choose by surrounding task and clarity, not a universal speed claim.

The conventional Z search stores $O(n + m)$ combined tokens and values, although an implementation can index pattern, separator, and text through a virtual sequence to avoid one copy. It still needs the Z array when callers consume prefix lengths later. If only match positions matter under strict streaming limits, KMP has the simpler state boundary.

Treat Rolling Hash as a Filter with a Collision Policy #

A polynomial rolling hash represents a token sequence using a base B and modulus M. For token codes x[i], define prefix hashes:

With precomputed powers of B, the hash of half-open window [left, right) is:

Adjust negative remainders according to the language. This normalization lets every length-m text window be compared with the pattern hash in $O(1)$ after $O(n + m)$ preprocessing. A sliding implementation can instead remove the outgoing token and add the incoming one without storing every prefix.

Prefix hashes are easiest when arbitrary substring lengths will be queried because powers align both windows to the same polynomial position. A fixed-length scanner can keep only one rolling value and the power for the outgoing token. In either form, token encoding must reserve a consistent value for every token; changing encoding between pattern and text invalidates comparison before collision probability is relevant.

Unequal hashes prove difference; equal hashes do not prove equality because the range is finite. Three honest contracts are:

1. Accept a documented collision probability, typically using two independent moduli or a wide randomized hash.
2. Verify every hash-equal candidate token by token, making returned matches exact.
3. Use a deterministic algorithm such as KMP or Z when adversarial worst-case guarantees matter.

Verification restores exactness but not deterministic linear time: many colliding windows can force $O(nm)$ comparisons. A randomized seed hinders precomputation and double hashing reduces accidental collisions, but unverified equality remains probabilistic.

Arithmetic must match the design. Defined unsigned overflow can implement modulo $2^{64}$. JavaScript multiplication loses integer precision beyond 53 bits, requiring bigint, careful 32-bit operations, or a tested library. Prime-modulus code must prevent intermediate overflow.

Rolling hashes become especially valuable when one text supports many substring-equality queries, when documents are chunked for deduplication, or when multiple candidate patterns share preprocessing. For one exact pattern scan, KMP or Z often offers a simpler guarantee with similar asymptotic work.

Make Unicode and Normalization Explicit #

Unicode permits several tokenizations. UTF-8 search reports byte offsets. JavaScript indexes UTF-16 code units, where a supplementary code point occupies two units. [...value] yields code points, while a displayed grapheme can still contain several code points.

Canonical equivalence is separate from tokenization. Precomposed é and e followed by a combining acute accent are different code-point sequences but may be considered equivalent text. Normalize both pattern and text to the same form, such as NFC, if that matches the product contract. Normalization can change length, so offsets in normalized text do not automatically map to offsets in the original input.

When callers need highlights in the original string, transformation should produce both search tokens and an offset map. Each transformed token records the original half-open span that contributed to it. A match then maps its first and last token back to source boundaries. Without that map, returning a normalized index as though it were an original UTF-16 or byte offset is a contract bug.

Case mappings can change length and differ by language. State comparison policy at the wrapper, transform before preprocessing, and preserve an offset map when results must highlight original text.

Grapheme segmentation such as Intl.Segmenter aligns display units but adds cost and does not equate confusable characters. Exact matching should not silently apply compatibility or confusable folding, especially for identifiers.

Chunked input adds a decoding boundary. A UTF-8 code point may span byte chunks, and a grapheme cluster may span decoded chunks. Feed bytes through a streaming decoder before code-point matching, and retain segmentation context when matching graphemes. The matcher cannot repair tokens that were split incorrectly upstream.

Choose by Workload, Then Test the Guarantee #

Use KMP when one pattern is reused, text arrives incrementally, or deterministic linear scanning with $O(m)$ auxiliary memory is the clearest contract. Use Z when prefix-match lengths are themselves useful or a batch combined sequence fits naturally. Use rolling hashes when substring comparisons or many queries can amortize text preprocessing and the collision policy is acceptable.

Benchmarks must include preprocessing and allocation, separate one-shot latency from reuse throughput, and include repetitive inputs. Report tokenization, sizes, match density, runtime, and whether hash candidates are verified.

Correctness tests need more than one found and one missing word:

• Pattern longer than text, equal to text, length one, and empty under the chosen API rule.
• Match at index 0, at the final legal start, and no match.
• Overlapping matches such as aba in ababa and aaa in aaaaa.
• Repetitive mismatch cases such as long runs of a followed by different final tokens.
• Patterns with no border and with several nested borders.
• Separator-like input tokens for the Z implementation.
• Unicode cases across byte, code-unit, code-point, normalization, and grapheme boundaries.
• Rolling-hash collisions forced with a tiny test modulus, both with and without verification.

A strong property test generates small token arrays and compares KMP, Z, and verified rolling hash with a nested-loop oracle. Assert every index is in range and its slice equals the pattern. The independent oracle prevents shared convention mistakes.

White-box tests can compare the prefix function and Z values against naive definitions for short random sequences. For KMP streaming, split the same text at every possible chunk boundary and require identical absolute results. For rolling hashes, compare every extracted window hash with a directly recomputed hash and test remainder normalization.

Collision tests should use a deliberately tiny modulus so distinct windows with equal hashes are easy to find. Unverified mode must demonstrate its documented false-positive possibility; verified mode must reject the same candidates. Repeat with randomized seeds only after deterministic fixtures cover the arithmetic, because an unpredictable test collision is not a reliable regression case.

Bound pattern and text size, retained preprocessing, and result count. A one-token pattern can produce nearly n overlaps and exhaust memory despite linear scanning, so offer iteration, callbacks, first-match mode, or a result limit. Treat user-controlled hashes as adversarial and avoid logging searched text.

KMP turns borders into failure links, Z turns a matched interval into prefix lengths, and rolling hash turns windows into fingerprints. Define tokens and offsets first, preserve deterministic guarantees where required, and verify hash candidates when equality must be exact. Algorithm choice then follows preprocessing needs and guarantee level.