Deterministic Linear-Time Missing Value Replacement in Strings

Given a finite alphabet, a list of forbidden strings, and two contexts u and v, the missing value replacement problem asks for a shortest string having prefix u and suffix v and containing no forbidden substring. Overlap between the contexts is permitted. We give a deterministic linear-time algorithm on a word RAM with one word per input symbol. For an explicitly listed alphabet of size A and total dictionary and context length M, the algorithm uses O(A + M + 1) time and auxiliary words and returns an explicit shortest witness or reports impossibility. For a polynomially bounded canonical integer alphabet specified by its size, the bound is O(M + 1). The main construction represents the reverse transitions of the safe Aho-Corasick automaton by O(L + 1) labeled intervals, where L is the total forbidden-pattern length. A deletion-only successor structure supports reverse breadth-first search in linear total time. Failure-subtree exclusions identify compatible terminal states, and a separate overlap check ensures global shortestness. An input-probe lower bound establishes worst-case time optimality up to constant factors in this representation. A C++ implementation and finite checks using a separate literal-history oracle accompany the proof. The supplementary material contains the editable HTML manuscript, BibTeX references, the endpoint-marker comparison note, C++17 implementation, audit and test scripts, retained synthetic test data/results, and reproduction instructions. The paper and mathematical supporting materials are licensed under CC BY 4.0. The software, tests and reproduction instructions are licensed under MIT. See LICENSES.md in the supplement for details.