String Matching & KMP Automata lab report

1. Title and aim

Empirical Analysis of String Matching Algorithms: Knuth-Morris-Pratt (KMP) Prefix Automata, Boyer-Moore Bad Character / Good Suffix Heuristics, Rabin-Karp Rolling Hash, and Asymptotic Text Search Complexity. To investigate the theoretical foundations and microarchitectural mechanics of exact string matching algorithms, evaluate the Knuth-Morris-Pratt (KMP) prefix function π-array, contrast KMP with Boyer-Moore sublinear shift heuristics and Rabin-Karp rolling hashes, and empirically verify the linear comparison scaling law C(n) = k_kmp · n + C_0 = 1.0000 · n + 20.0000 comparisons across text stream lengths n ∈ [500, 10000] characters for pattern length m = 20.

2. Abstract

Seven benchmark trials were generated across text stream lengths n = 500 to n = 10000 characters with fixed query pattern length m = 20 characters (total comparisons C from 520 to 10020 operations). An ordinary least-squares regression of character comparisons against text stream length yielded an empirical scanning slope of 1.0000 comparisons/char and an intercept of 20.0000 comparisons, demonstrating exact agreement with the theoretical Knuth-Morris-Pratt complexity model C(n) = n + m (difference = 0.0000%). The empirical telemetry confirms that KMP eliminates text pointer backtracking entirely, advancing the stream pointer monotonically while resolving character mismatches via the failure function π in amortized linear time O(n + m).

3. Apparatus and fixed settings

• KMP Failure Function (π-Prefix Array) Synthesizer: Deterministic preprocessor computing the longest proper prefix that is also a suffix for all pattern prefixes P[0..q] in O(m) time.
• Boyer-Moore Bad Character & Good Suffix Lookup Tables: Dual-heuristic jump tables calculating right-to-left shift vectors based on mismatch character identity and matching suffix patterns.
• Rabin-Karp Rolling Hash & Modular Arithmetic Register: Hardware polynomial hash accumulator evaluating rolling substring signatures modulo large prime q using Horner's method.
• Aho-Corasick Multi-Pattern Trie & Dictionary Matcher: Automaton compiler constructing trie hierarchies, failure transitions, and dictionary output links for simultaneous multi-string scanning.
• Hardware SIMD Vector Matching Unit (AVX-512 / ARM Neon): Microarchitectural vector execution register executing 64-byte parallel character comparisons via byte-mask instructions.
• Deterministic English Corpus & Synthetic Text Generator: Configurable text stream synthesizer generating controlled alphabets, natural language corpora, and pathological repeated-prefix sequences.
• Corpus text stream T[0 .. n-1] synthesized from an English alphanumeric alphabet (|Σ| = 62) with uniform character entropy.
• Target search query pattern P[0 .. 19] of fixed length m = 20 characters with precomputed π-prefix failure array.
• Knuth-Morris-Pratt comparator engine maintaining non-backtracking text pointer i ∈ [0 .. n-1] and pattern state pointer j ∈ [0 .. m-1].
• Hardware microarchitectural profiler monitoring L1 data cache line hits, branch mispredictions, and comparison counter registers.

4. Theory and graph choice

The exact string matching problem is one of the most fundamental challenges in computer science, lying at the heart of text editors, operating system grep utilities, web search engines, genomic sequence alignment (BLAST), and network intrusion detection systems (Snort). Given an input text stream T[0 .. n-1] of length n and a target query pattern P[0 .. m-1] of length m over a finite alphabet Σ, the objective is to identify all valid alignment shifts s ∈ [0 .. n - m] where T[s .. s + m - 1] = P[0 .. m - 1]. The naive brute-force algorithm tests each shift candidate sequentially, comparing characters until a match is confirmed or a mismatch occurs. In the worst case—such as searching for P = 'a^(m-1)b' in T = 'a^n'—naive matching requires Θ((n - m + 1) · m) character comparisons, repeatedly rewinding the text pointer and incurring severe memory bus stall cycles. In 1977, Donald Knuth, James Morris, and Vaughan Pratt published the Knuth-Morris-Pratt (KMP) algorithm, proving that string matching can execute in strictly linear O(n + m) time without ever rewinding the text pointer. KMP achieves this by precomputing the Failure Function π[0 .. m-1], where π[q] records the length of the longest proper prefix of P[0 .. q] that is also a proper suffix of P[0 .. q]. When a mismatch occurs between text character T[i] and pattern character P[j], the failure table instantaneously identifies the next valid pattern alignment j' = π[j-1], preserving all verified prefix information and advancing the search without redundant comparisons. Symmetrically, the Boyer-Moore algorithm (1977) scans pattern characters from right to left, utilizing the Bad Character Rule and Good Suffix Rule to skip up to m characters per mismatch, achieving sublinear O(n/m) average-case time. Meanwhile, the Rabin-Karp algorithm (1987) treats character substrings as polynomial numbers, computing rolling hashes in O(1) time via Horner's rule. In this laboratory investigation, students benchmark KMP prefix automata across text scales n ∈ [500, 10000] with fixed m = 20, verify the exact linear scaling law C(n) = 1.0000 · n + 20.0000 comparisons via ordinary least-squares regression, explore failure link state transitions, and analyze CPU cache line streaming and SIMD vectorization.

The mathematical regression fits the linear model y = mx + b, where x = n represents the input text stream length in characters, y = C represents total character comparison operations, m represents the scanning slope k_kmp, and b represents the failure array preprocessing comparison overhead (theoretically C_0 = 20.0000 comparisons). The gradient has physical units comparisons/char.

5. Method

1. Load the target pattern P[0 .. 19] of length m = 20 characters. Execute the failure function preprocessor to compute π[0 .. 19], logging exactly C_0 = 20 preprocessing comparison operations into the telemetry register.
2. Adjust the independent variable control slider to configure the input text stream length n between 200 and 10,000 characters across the designated benchmark sample points.
3. Trigger the KMP matching engine. Traverse text pointer i from 0 to n-1, comparing text character T[i] with pattern character P[j]. On match, advance j; on mismatch, redirect j to π[j-1] without decrementing text pointer i.
4. Read the total character comparison count C(n) from the algorithmic comparator register upon stream completion, verifying that C(n) = n + m comparisons.
5. Log the independent text length n and dependent comparison count C(n) into the laboratory notebook table and plot the corresponding data coordinate.
6. Perform ordinary least-squares regression across all seven benchmark trials to extract the text scan slope k_kmp and intercept C_0, evaluating residual variance, cache throughput, and comparative algorithm trade-offs.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 1.1215e-10. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 6.3053e-07.

Propagating the fit parameters yields a fit standard error of 1.1215e-10 comparisons/char, with an ideal coefficient of determination R² = 1.000000.

In discrete string matching algorithm analysis, the character comparison count C(n) = k_kmp · n + C_0 = 1.0000·n + 20.0000 for Knuth-Morris-Pratt scanning is an exact mathematical invariant under uniform text models with pattern length m = 20. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete character equality evaluations in virtual registers. However, in physical semiconductor microprocessors, wall-clock string search latency is strongly modulated by memory hierarchy and pipeline dynamics: (1) CPU L1/L2 data cache hit ratios and spatial prefetching: sequential text scanning (incrementing pointer i from 0 to n-1) achieves near 100% L1 cache line hit rates (~1 ns latency) as hardware prefetchers stream contiguous 64-byte lines ahead of execution; (2) Branch predictor mispredictions during mismatch redirection: when character mismatches trigger failure table lookups (`j = pi[j - 1]`), conditional branch instructions (`if (P[j] == T[i])`) can cause pipeline flushes (15–20 CPU cycle penalty) on irregular text; (3) Sublinear window skipping in Boyer-Moore: on large alphabets, right-to-left scanning skips up to m characters per mismatch via bad-character tables, executing significantly faster than KMP in wall-clock time; and (4) Hardware SIMD vectorization: modern CPUs utilize AVX-512 and ARM Neon vector instructions (`_mm512_cmpeq_epi8_mask`) to evaluate 64 text characters in a single clock cycle, operating an order of magnitude faster than scalar comparison loops. Ordinary least-squares linear regression of observed character comparisons against text length n across stream lengths from 500 to 10,000 characters yields an empirical scaling slope k_kmp = 1.0000 comparisons/char with zero residual variance (R² = 1.00000), verifying the asymptotic linear time complexity bound Θ(n + m) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of the Knuth-Morris-Pratt automaton and asymptotic string processing complexity. In KMP text scanning with query pattern length m = 20, the text pointer i advances strictly from 0 to n - 1 without ever decrementing. Upon encountering a character mismatch between T[i] and P[j], the pattern pointer falls back to state j' = π[j - 1], preserving all previously matched substring prefixes. Because each character mismatch fallback decreases the pattern state j while i continues advancing, amortized analysis via the potential function Φ = j proves that the total number of character comparisons is strictly bounded by 2n. On uniform text streams, the empirical scanning slope m = 1.0000 confirms that exactly one comparison is executed per text character on average, while the intercept b = 20.0000 matches the exact preprocessing comparison cost of constructing the 20-element failure table π[0 .. 19]. The regression fit exhibits zero residual variance (R² = 1.00000). Comparative paradigm analysis reveals critical microarchitectural trade-offs across string matching architectures: Naive brute-force search suffers catastrophic Θ(n · m) worst-case degradation when processing self-similar prefixes, rewinding the text pointer and evicting CPU L1 data cache lines. In contrast, KMP guarantees strictly linear O(n + m) streaming performance with O(1) auxiliary working memory, making it ideal for unbuffered network sockets and Unix pipes. Boyer-Moore achieves sublinear O(n/m) average-case time on large alphabets by scanning right-to-left and jumping forward by up to m positions per bad-character mismatch. Rabin-Karp provides O(1) sliding window updates via polynomial rolling hashes, enabling seamless multi-pattern and 2D matrix matching. Aho-Corasick scales multi-pattern dictionary matching to wire speed by compiling pattern sets into trie automata with failure and output links. Finally, modern hardware implementations leverage SIMD vectorization (AVX-512 and ARM Neon) to compare 64 characters in parallel per clock cycle, demonstrating how hardware and algorithm co-design maximizes search throughput.

11. Precautions and limitations

• Verify that the KMP failure function π[0 .. m-1] is fully precomputed before scanning the text stream; using uninitialized failure indices causes illegal memory jumps.
• Ensure 64-bit integer arithmetic or strict modulo prime reductions are applied in rolling hash calculations to prevent catastrophic integer overflow bugs.
• When implementing the Boyer-Moore Good Suffix table, carefully account for pattern prefixes that match suffixes of the matched substring to avoid overshooting valid match occurrences.
• Account for zero-terminated C-strings and multibyte UTF-8 encodings; string matching algorithms operating on raw byte arrays must not treat UTF-8 continuation bytes as ASCII characters.

The simulated execution environment models idealized scalar CPU comparison registers where every character equality evaluation executes with deterministic cost of 1 operation (C(n) = n + m). In physical semiconductor microprocessors, wall-clock execution latency is modulated by CPU L1 data cache hit ratios during text buffer streaming, hardware branch predictor mispredictions during character mismatch redirects (`if (P[j] == T[i])`), Translation Lookaside Buffer (TLB) page table walks across large corpus buffers, and hardware SIMD vector unit availability. In the Knuth-Morris-Pratt (KMP) text search benchmark with pattern length m = 20, the algorithm executes in two distinct phases: (1) Preprocessing the failure function π[0 .. m-1], which consumes exactly C_0 = m = 20 comparisons; and (2) Scanning the text stream T[0 .. n-1], where the text pointer i strictly advances from 0 to n - 1. Because the text pointer never moves backward and pattern pointer fallback via π[j-1] is bounded by prior increments, the scanning phase executes with an empirical scaling rate of exactly k_kmp = 1.0000 comparison per text character on uniform corpus data. Total character comparisons scale strictly as C(n) = 1.0000 · n + 20.0000 comparisons, yielding an exact linear relationship with zero residual variance across all benchmark trials.

12. Conclusion

This laboratory investigation quantitatively verified the failure function mechanics, state transition dynamics, and asymptotic linear scaling of string matching automata. Through systematic benchmarking across text streams from n = 500 to 10000 characters, we verified the empirical text scan slope k_kmp = 1.0000 comparisons/char and failure table intercept C_0 = 20.0000 comparisons with an ideal R² = 1.00000. The investigation established the microarchitectural superiority of non-backtracking automata, contrast heuristics, and vector extensions over naive quadratic scanning, proving why KMP, Boyer-Moore, Rabin-Karp, and Aho-Corasick form the foundational core of modern computational genomics, search engines, and network intrusion detection systems.