{"id":"58a671a9-08e5-412c-88fe-3fbddc489b3e","arxiv_id":"1908.05930","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A new sampled string matching algorithm filters matches using distances between pivot characters, claiming linear worst-case and optimal average complexity with 2.8% to 11% extra space.","lead":"This paper introduces a new way to speed up exact text search by storing the distances between consecutive occurrences of a chosen pivot character, then checking only candidate positions in the original text. It reports faster searching than a standard online algorithm using only a few percent of extra space.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reconstruction of pivot positions fails whenever a pivot occurs at a multiple of the block size k, breaking the filter's correctness.","rationale":"I read the paper as claiming that the distance-sampled sequence is a lossless filter: any true occurrence of the pattern produces a matching sampled sequence, and the verification step recovers the original text position from the sampled data. For that claim to hold, two things must work: the distance sequence must be reconstructed without wrap-around errors, and the absolute pivot positions must be recovered correctly from the residue representation. The reader's weakest_assumption focuses on the first requirement, the Δ(i) < k condition. That condition is at least explicitly stated, and for any valid occurrence the pattern's pivot distances inherit it from the text, so it is not the most decisive problem. The second requirement is where the paper has an internal inconsistency: Definition 1 fixes residues in 0..k−1, but Corollary 1 and Get-Position treat residue 0 as if it were a position at the start of a block instead of the end. At any pivot occurrence whose position is a multiple of k, the reconstructed position is off by k. This is not a subtle asymptotic issue; it is a concrete correctness failure on ordinary 1-based inputs, independent of the Δ(i) < k assumption. The distance values in Corollary 2 are consistent with the 0-residue convention, so the filter itself can still find the right sampled positions, but the subsequent mapping to the original text is wrong. Because the central claim requires the filter to be lossless and the verification to start at the correct text offset, this bug is load-bearing. It is likely fixable, but as written the preprint does not meet the bar for acceptance. The reader's REJECT verdict therefore stands, though for a different weakest point than the one identified in the reader's report.","tokens_in":16538,"tokens_out":11460,"duration_ms":119842,"concrete_test":"Unit-test the reconstruction on y = 'bcdea', k = 5, with pivot 'a'. Compute-Position-Sampling gives ˙y = [0] and τ = [1]; Get-Position(τ, 1, ˙y, 1) returns p = 0 instead of 5. Running the published Search-1 on pattern 'a' therefore does not report the occurrence at position 5. Equivalently, change the formula to treat ˙y = 0 as residue k (or store residues 1..k) and rerun the same test: the occurrence is reported. This single check decides whether Corollary 1 is correct.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 1 and the Get-Position pseudocode in Fig. 1 reconstruct the absolute position of a pivot occurrence as δ(j) = (τ[b]−1)k + ˙y[j], where ˙y[j] = δ(j) mod k is defined to lie in {0,...,k−1}. This is wrong for the residue 0: if δ(j) = qk, then ˙y[j] = 0 and the formula returns (q−1)k, not qk. For example, with k = 5 and the pivot at position 5, ˙y[1] = 0 and τ[1] = 1, but Get-Position returns 0. Since the text is 1-based, position 5 is valid and should map to block 1 with residue 5, not residue 0. Every Search-0, Search-1, and Search-2+ routine that calls Get-Position then verifies at the wrong text offset whenever the relevant pivot lies on a block boundary; valid occurrences are missed and bogus ones may be reported. This holds even when the stated condition Δ(i) < k is satisfied, because the error is in absolute-position reconstruction, not in distance unwrapping. The distance values in Corollary 2 happen to be correct for residue 0, but the algorithm cannot translate a sampled distance occurrence into the original text position to verify it. Thus the lossless-filter central claim fails as written for arbitrary 1-based texts; it is fixable by storing (δ(j)−1) mod k + 1 or special-casing 0, but the preprint does not do so.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new sampled string matching algorithm based on sampling the distances between consecutive occurrences of a chosen pivot character. The text is divided into blocks of size k; the sampled sequence stores the position of each pivot occurrence modulo k, and a block-mapping table τ supports reconstruction of the original pivot positions. For patterns containing the pivot at least twice, the algorithm searches for the sampled pattern (the sequence of distances between consecutive pivots) in the sampled text, then verifies candidate positions in the original text. The paper claims O(n) worst-case and O(n log_σ m / m) average-case time under suitable conditions, while using 2.8%–11% of the text size as extra space, and reports experiments showing speedups over the Ots algorithm of Claude et al.","tokens_in":16789,"tokens_out":16530,"duration_ms":156453,"significance":"The characters-distance sampling idea is simple and potentially useful: it offers a very compact partial index and the experiments indicate practical speedups on English text, especially for short patterns. The asymptotic claims, if established, would be a nice complement to existing sampled string matching results. However, the manuscript contains several load-bearing correctness errors in the core reconstruction formula and in the Search-0 pseudocode, as well as a false lemma and an unproven worst-case theorem, so the current version cannot be accepted as a correct and complete algorithm.","major_comments":[{"comment":"The reconstruction formula δ(j) = (τ[b] − 1)k + ˙y[j] is incorrect for pivot occurrences whose position is a multiple of k, because in that case ˙y[j] = 0 and the formula returns (τ[b] − 1)k instead of τ[b]k. For example, with k = 5 and δ(j) = 5, the formula returns 0. Since Get-Position is used by all three search procedures to determine the verification offset, this can cause valid occurrences to be missed or spurious verifications to be performed, invalidating the lossless-filter claim as written. The fix is to store residues in {1, . . . , k} or to special-case the zero residue.","section":"§3.1, Corollary 1 and Fig. 1"},{"comment":"The main loop of Search-0 begins at i = 2 and δ1 is never initialized, so the interval before the first pivot occurrence is never searched; any occurrence of x in y[1..δ(1) − 1] is missed. The loop header 'for i≤2 to nc' also contains a typo. The procedure must either start at i = 1 after computing δ1 or handle the first interval separately.","section":"§3.3, Search-0 (Fig. 5)"},{"comment":"Lemma 2 has a sign error: from Corollary 1 the correct difference is ˙y[i+1] + (τ[b] − τ[a])k − ˙y[i], not ˙y[i+1] + (τ[a] − τ[b])k − ˙y[i]. The stated formula gives wrong values when the two pivots are in different blocks; for example, with k = 5, positions 1 and 7 give −4 instead of 6. Although Corollary 2 is correct and is what the search uses, the lemma as printed is false and should be corrected.","section":"§3.1, Lemma 2"},{"comment":"The proof of the O(n) worst-case bound is not supplied. It asserts that a KMP-style Verify can 'remember all positions of the text which have already been verified,' but no such mechanism is defined, and the preceding line admits that the naive bound is O(nc·m). Since the number of candidate matches can be Θ(nc), the claimed O(n) worst case needs a precise amortized argument or a different verification strategy.","section":"§3.3, Theorem 3"},{"comment":"The correctness of the distance filter depends on relation (6), which is derived under the assumption Δ(i) < k for all consecutive pivot occurrences in the text. The paper states only that the pivot rank 'must be chosen' to satisfy this condition and does not guarantee it for arbitrary inputs; the complexity theorems also do not state this condition explicitly. Please clarify the exact set of inputs for which the algorithm is correct, or extend the method to handle wrap-around distances.","section":"§3.2, Corollary 2 and Theorem 3"}],"minor_comments":[{"comment":"The first distance is incorrectly computed as δ(1) − δ(0) = 3 − 1 = 2; with the stated text δ(1) = 1 and the correct expression is δ(2) − δ(1) = 3 − 1 = 2.","section":"§3.1, Example 4"},{"comment":"Verify's loop tests x[i] against y[s+i], which implies s is a zero-based offset, yet Search-1 passes a one-based start (δ_{i−1} − α + 1) and Search-2 passes δ_i − α; this indexing convention should be made consistent.","section":"Fig. 4 and Fig. 6"},{"comment":"In §3.3 the BDM algorithm is cited as [12], but reference [12] is Horspool's algorithm; the optimal-average-case citation should be to [6].","section":"§3.3, references"},{"comment":"The text refers to 'Table 8' when discussing the space-consumption figure; it should be Figure 8.","section":"§4.1, Figure 8"},{"comment":"The conclusion says the algorithm 'may require only 5% of additional extra space,' while the abstract reports 11% to 2.8%; these numbers should be harmonized.","section":"Conclusion"},{"comment":"Several pseudocode typos remain: 'for i≤2' should be 'for i←2' in Figs. 5 and 6, and line 10 of Fig. 6 uses the undefined symbol 'pi−1'.","section":"Pseudocode"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be an early preprint with numerous typos and some incorrect pseudocode. The core idea is salvageable, and the reported experiments may be reproducible once the algorithms are fixed, but the current text contains multiple load-bearing errors in the central reconstruction and search procedures. I would be willing to review a revised version that corrects the residue-zero bug, the Search-0 loop, the Lemma 2 sign error, and the Theorem 3 proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe distance-sampling idea is genuinely new, but the current preprint is not correct as written: the position reconstruction in Get-Position fails for pivot occurrences exactly on block boundaries, and Search-0's loop is broken. Those are load-bearing, not cosmetic.\n\nWhat's new and good: the scheme samples distances between consecutive occurrences of a pivot character, storing positions modulo k plus a block-mapping table. That's not in Claude et al.'s alphabet sampling. The space figures (2.8–11% vs 14.8%) are credible, and the experiments on a 5MB English text show real speedups over Horspool and Ots. The three search cases are a sensible organization.\n\nNow the soft spots. Corollary 1's formula δ(j) = (τ[b]−1)k + ˙y[j] fails when δ(j) mod k = 0. Since ˙y[j] ∈ {0,...,k−1}, a pivot at position qk gives residue 0 and the formula returns (q−1)k. The stress-test example is correct: k=5, pivot at position 5 returns 0. Every Search-0/1/2+ call to Get-Position is then wrong at those occurrences.\n\nSearch-0's pseudocode has a separate bug: the loop starts at i=2, so δ1 is never computed and the text prefix before the first pivot is never searched. Search-2+ has an off-by-one in verification: it uses y[δ_i − α] instead of δ_i − α + 1.\n\nThe theory is also shaky. Lemma 2's formula has a sign error (τ[a]−τ[b] should be τ[b]−τ[a]). Theorem 3's O(n) worst case rests on an unspecified KMP-style verification that remembers already-checked positions, with no details. The average-case optimality claims are conditional on assumptions (k≥σ, Δ(i) \\dot{y}[i]$, and $\\Delta(i) = \\dot{y}[i+1] + k - \\dot{y}[i]$ otherwise. The paper proves this reconstruction is exact whenever every consecutive pivot gap in the text is strictly less than $k$, and that the resulting filter never discards a true occurrence. It then searches the reconstructed distance sequence for the pattern's distance sequence and verifies each candidate in the original text, claiming that the whole procedure inherits linear worst-case and optimal average-case bounds from the underlying string-matching routine.","pith_inferences":["Editorial inference: the same $(\\dot{y}, \\tau)$ structure gives near-constant recovery of pivot positions, so it could be promoted to a lightweight sparse index that counts or locates pivot-anchored matches without scanning the text.","Editorial inference: an adaptive block size chosen after measuring the pivot's maximum gap would remove the main correctness restriction while keeping byte-level storage only when gaps are actually small.","Editorial inference: a practical implementation should detect any text gap that reaches $k$ during preprocessing and fall back to a larger $k$ or to the zero- and one-pivot search strategies; the paper does not analyze such a safeguard.","Editorial inference: the approach is naturally suited to wide alphabets; on low-entropy alphabets such as DNA the pivot occurs too often, so false-positive verification would dominate, a limitation the paper itself states."],"forward_implications":["Choosing the most frequent character as pivot gives the shortest sampled text (one byte per pivot occurrence), about 11% of text size; choosing a rank-20 pivot lowers this to about 2.8%.","If the underlying search routine is linear in the worst case, the sampled search inherits the same $O(n)$ bound; if the routine is optimal on average, the sampled search inherits $O(n \\log_\\sigma m / m)$ for patterns up to a few hundred characters when $k=256$.","On English text the measured search times are 32% below plain Horspool for 2-character patterns and 91% below for 256-character patterns, with preprocessing faster than the earlier occurrence-sampling approach.","Preprocessing time is lower than the earlier occurrence-sampling method by 15–50%, mainly because the new sampled structure is smaller."],"supporting_citations":[{"why":"Defines the sampled-string-matching problem and the occurrence-sampling baseline whose space and speed the paper compares against.","marker":"[5]"},{"why":"Provides the linear worst-case search routine whose complexity the new algorithm inherits in the complexity theorems.","marker":"[15]"},{"why":"Provides the backward-dawg-matching algorithm cited as the optimal average-case routine the complexity argument relies on.","marker":"[6]"},{"why":"Supplies the lower bound $\\Omega(n \\log_\\sigma m / m)$ that defines the optimal average-case target.","marker":"[21]"},{"why":"Provides the Horspool algorithm used as the practical underlying search routine and as the speed baseline in the experiments.","marker":"[12]"}],"fun_headline_variants":["Sample gaps between pivot characters: text search up to 9x faster","Pivot-gap sampling: 9x faster online search, only 2.8-11% extra space","Character-distance sampling trims search time by 9x, space to 2.8%","Online text search: distance sampling of pivot chars gives up to 9x speedup","Speed up string matching 9x with character-gap sampling, small index"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The distance filter is exact only when every distance between two consecutive pivot characters in the text is strictly less than the block size $k$; if a pivot gap reaches or exceeds $k$, relation (6) wraps modulo $k$ and can reconstruct the wrong distance, causing valid matches to be missed.","fun_headline_variants_meta":{"raw":{"variants":["Sample gaps between pivot characters: text search up to 9x faster","Pivot-gap sampling: 9x faster online search, only 2.8-11% extra space","Character-distance sampling trims search time by 9x, space to 2.8%","Online text search: distance sampling of pivot chars gives up to 9x speedup","Speed up string matching 9x with character-gap sampling, small index"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001615,"raw_usage":{"total_tokens":6463,"prompt_tokens":1016,"completion_tokens":5447,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":5347}},"tokens_in":632,"tokens_out":5447,"duration_ms":41321,"temperature":1.0,"reasoning_tokens":5347,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:00:01.254690+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $k=3$, choose 'a' as the pivot, and run the algorithm on pattern $x=\\texttt{abbba}$ (a at positions 1 and 5, true gap 4) and text $y=\\texttt{abbbab}$ (a at positions 1 and 5). The pattern's sampled distance is 4, while relation (6) reconstructs the text gap as $(5 \\bmod 3) - (1 \\bmod 3) = 1$, so the search reports no candidate and misses the occurrence at position 1; observing that miss on this input shows the bounded-gap condition is essential to the lossless-filter claim.","supporting_citations":[{"cited_title":"Claude, G","cited_arxiv_id":null,"evidence_quote":"Defines the sampled-string-matching problem and the occurrence-sampling baseline whose space and speed the paper compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the linear worst-case search routine whose complexity the new algorithm inherits in the complexity theorems."},{"cited_title":"Crochemore, A","cited_arxiv_id":null,"evidence_quote":"Provides the backward-dawg-matching algorithm cited as the optimal average-case routine the complexity argument relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the lower bound $\\Omega(n \\log_\\sigma m / m)$ that defines the optimal average-case target."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Horspool algorithm used as the practical underlying search routine and as the speed baseline in the experiments."}],"review_version":1}