--- title: "algorithm-kmp — Mova code model" description: "Mova code model of algorithms/src/kmp/mod.rs: components with their labels, obernants and the model text." url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/kmp/mod.rs.groupant/" --- Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants** This page as HTML: # algorithm-kmp The groupant beside algorithms/src/kmp/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks. ## Facts - **kind:** groupant - **status:** partial descriptive instance - **source:** [`algorithms/src/kmp/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/kmp/mod.rs) - **source SHA-256:** `ec37c7bc4399e5fa…` - **repository folder:** [`algorithms/src/kmp/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/kmp/mod.rs.groupant) - **repository commit:** `855da7bd4a7b` > **Implementation material.** A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised. ## Components | component | label | where | |---|---|---| | **approximant** | partial | [approximant](#approximant) | | **ast** | partial | `syntax.json` | | **descriptant** | present | [descriptant](#descriptant) | | **invariant** | partial | [approximant](#approximant) | | **tests** | existing checks referenced | [tests](#tests) | ## Obernants The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views. | id | type | label | where | |---|---|---|---| | `behavior_complement` | behavior_complement | partial source derived model | [behavior_complement](#behavior-complement) | | `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) | | `boundary_fiber` | boundary_fiber | partial source derived model | [boundary_fiber](#boundary-fiber) | | `overlap_constraint` | overlap_constraint | partial source derived model | [overlap_constraint](#overlap-constraint) | | `byte_relabeling` | byte_relabeling | partial source derived model | [byte_relabeling](#byte-relabeling) | ## Model text ### descriptant #### Algorithm file groupant This is the original standalone kmp implementation. The authoritative Rust source lives outside this sidecar. Forward recurrence, invariant and cost are in approximant.md; five typed models are in models.md. The manifest binds the current source hash and partial syntax projection. Syntax extraction does not expand macros, resolve names or prove semantic correctness. Epoch 2026-10-29: prospective expectations were saved outside the repository before writing source. Independent finite oracles passed twice. A compiled source mutation failed the same suite, demonstrating a red gate. These bounded observations support the recurrence; they do not prove all inputs. Resource exhaustion, expensive element comparisons and complete preimage execution are explicit gaps. Preserve this evidence when extending the implementation. Composition: conjunction of the source identity, recurrence and invariant gives a conditional implementation model; typed models answer distinct questions about that relation. Their statements do not add to a global inverse identity. Cost and tests qualify the model, rather than proving a larger caller's wiring. Test extraction epoch, 2026-10-29: inline tests moved to sibling tests.rs with their own source-bound groupant and registry entry; this module delegates through a cfg(test) declaration. Production prefix remains byte-identical. Two new tests extend bounded coverage; no production fix or timing gain is claimed. ### approximant #### Forward, invariant and cost Forward: construct longest proper prefix/suffix lengths for every pattern prefix, scan the text, emit every full match and resume from its longest border. Invariant: matched is the length of a pattern prefix equal to a suffix of the scanned text; after emitting, fallback preserves candidate overlapping matches. The prefix table obeys 0<=prefix[i]<=i and identifies the longest proper border. Time O(n+m+z), where z is output length (z<=n+1); auxiliary space O(m), plus O(z) output. Each fallback decreases matched, charged against prior increments. No wall-clock benchmark or speedup is claimed. ### models ## KMP models Subject/revision: mod.rs SHA-256 in manifest.json. Observation is a single terminating call, not intermediate execution traces. Allocation success is assumed. All five models are source-derived partial specifications; finite evidence below does not prove universal correspondence. ### behavior_complement Domain U: byte text t, byte pattern p, any proposed finite list L of offsets. Let W(t,p) be all i in ascending order with t[i..i+|p|]=p and 0<=i<=|t|-|p|, or every boundary 0..=|t| when p is empty. The operator C={(t,p,L) in U | L != W(t,p)} is an exact complement of the specification graph, a hypothesized inner bound on absent Rust behaviors under normal termination. Missing matches, duplicate offsets, wrong order and omitted overlaps are explicitly excluded. Oracle: exhaustive_windows, plus offset mutant. ### reverse_reconstruction Fix p and an observed list L. The compatible preimage is {t | W(t,p)=L}; no particular original text is recovered. For a finite alphabet and length bound, enumerate every text and retain equality. This is complete within that bounded domain, and generally many-to-one. Oracle: the window specification defining exhaustive_windows; explicit preimage enumeration is a future check. ### boundary_fiber Type: boundary_preimage. Fix empty pattern and observed length k of output. The preimage contains every text of length k-1 if k>=1, and none if k=0. This erases all byte information. Exact specification relation under normal termination. Empty and nonempty binary texts in exhaustive_windows are evidence. ### overlap_constraint Type: overlap_compatibility. Fix pattern p and two proposed starts i