algorithm-manacher

The groupant beside algorithms/src/manacher/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

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	bounded checked	Forward
ast	partial	`syntax.json`
cost	symbolic unmeasured	Cost
descriptant	present	descriptant
invariant	source derived	Invariant
tests	bounded executed	evidence

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
`nonbehavior`	behavior_complement	partial source derived	nonbehavior
`compatible_antecedents`	reverse_reconstruction	partial source derived	compatible_antecedents
`relabeling_boundaries`	metamorphic_relation	partial source derived	relabeling_boundaries
`joint_output_feasibility`	constraint_feasibility	partial source derived	joint_output_feasibility
`reversal_centers`	metamorphic_relation	partial source derived	reversal_centers
`interval_membership`	observation_projection	partial source derived	interval_membership
`palindrome_count_loss`	information_loss	partial source derived	palindrome_count_loss
`maximal_boundary_constraints`	boundary_exclusion	partial source derived	maximal_boundary_constraints

Model text

descriptant

manacher mod.rs epoch

2026-10-30. Repository search found no z_algorithm or manacher implementation in algorithms/src. Original std-only code, no unsafe, new dependencies or external solution imports. API and mathematical target were fixed before implementation: maximal prefix lengths or odd/even palindrome radii over bytes, with a monotone right frontier and linear predicted cost.

The mathematical combiner combines raw source, source-bound partial syntax, forward model, ordered typed obernants, invariants, cost and finite checks. The tests leaf is separate so a correct test model does not certify production. The first measured epoch supports the prediction on 9,841 bounded cases per algorithm and long constant fixtures; both compiled semantic mutants show red. No timing gain was measured. Future epochs must retain these observations and revise unsupported claims rather than convert them into proof.

Byte offsets deliberately permit spans inside UTF-8 encodings. Parent wiring belongs to integration. Macro bodies and semantic analysis remain gaps. All exact behavior is described directly; executable approximation profiles are absent.

Constraint and observation epoch, 2026-10-30

Constraints from different positions must be solved jointly: legal coordinate bounds can still be impossible. Distinct-class byte witnesses are complete only in the stated at-most-256-position domain; larger domains require quotient-graph coloring. Projection collisions preserve reverse ambiguity. Named Rust tests connect these models to production outputs without changing its API. Earlier exhaustive evidence remains useful. No runtime bug or performance improvement is claimed.

model

manacher mod.rs model

Forward

For byte sequence s of length n return odd/even vectors of length n. odd[i] is maximal r>=1 with palindrome s[i+1-r..i+r]; even[i] is maximal r>=0 with palindrome s[i-r..i+r]. The even center is immediately before i. Empty input yields two empty vectors.

Invariant

For each parity pass, earlier radii are maximal and [left,right) is a known palindrome with the greatest discovered right endpoint. A center inside it copies the reflected radius clipped at right-i; symmetry guarantees this lower bound. Further comparisons extend it maximally. Odd left=i+1-radius and even left=i-radius never underflow; right=i+radius<=n. Mirror indices use left+(right-1-i) or left+(right-i), avoiding overflowing left+right.

Cost

Two linear passes: O(n) byte comparisons, O(n) output words, O(1) auxiliary words. Each successful comparison beyond the mirror lower bound advances the right frontier; at most one failed comparison per center. No throughput measurement.

nonbehavior

Type: behavior_complement. Universe: finite byte inputs paired with arbitrary pairs of usize vectors. Excluded outputs have wrong lengths, zero odd radii, out-of-range spans, unequal symmetric byte pairs in a claimed span, or a radius whose next valid outer pair still matches. The model describes excluded behavior independently of negative tests.

compatible_antecedents

Type: reverse_reconstruction. Given two radius vectors of equal length n, compatible inputs are exactly byte strings of length n satisfying 1<=odd[i]<=min(i+1,n-i) and 0<=even[i]<=min(i,n-i), every symmetric equality inside every claimed span, and inequality of the next outer byte pair whenever that pair exists. Empty vectors admit empty input. Inconsistent equalities/inequalities admit no input; injective symbol relabelings exhibit nonunique antecedents.

relabeling_boundaries

Type: metamorphic_relation. Injective byte relabeling preserves both vectors. A constant string has odd[i]=min(i+1,n-i), even[i]=min(i,n-i). UTF-8 bytes need not share the character-level palindrome structure.

joint_output_feasibility

Type: constraint_feasibility. Domain: Radius vectors of common length n<=256, byte witnesses.

Relation: Require 1<=o[i]<=min(i+1,n-i), 0<=e[i]<=min(i,n-i). Union symmetric pairs in both parities and add inequality edges for next outer pairs when in bounds. Feasible iff no edge collapses to one class; distinct class bytes construct a witness. Larger n additionally requires 256-colorability; the bounded routine does not decide this.