Papers › Minimizers in Semi-Dynamic Strings
Minimizers in Semi-Dynamic Strings
Wiktor Zuba, Oded Lachish, Solon P. Pissis
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Minimizers sampling is one of the most widely-used mechanisms for sampling strings. Let S=S[0]…S[n-1] be a string over an alphabet Σ. In addition, let w≥2 and k≥1 be two integers and ρ=(Σᵏ,≤) be a total order on Σᵏ. The minimizer of window X=S[i. . i+w+k-2] is the smallest position in [i,i+w-1] where the smallest length-k substring of S[i. . i+w+k-2] based on ρ starts. The set of minimizers for all i∈[0,n-w-k+1] is the set ℳ_(w,k,ρ)(S) of the minimizers of S. The set ℳ_(w,k,ρ)(S) can be computed in 𝒪(n) time. The folklore algorithm for this computation computes the minimizer of every window in 𝒪(1) amortized time using 𝒪(w) working space. It is thus natural to pose the following two questions: Question 1: Can we efficiently support other dynamic updates on the window? Question 2: Can we improve on the 𝒪(w) working space? We answer both questions in the affirmative: 1. We term a string X semi-dynamic when one is allowed to insert or delete a letter at any of its ends. We show a data structure that maintains a semi-dynamic string X and supports minimizer queries in X in 𝒪(1) time with amortized 𝒪(1) time per update operation. 2. We show that this data structure can be modified to occupy strongly sublinear space without increasing the asymptotic complexity of its operations. To the best of our knowledge, this yields the first algorithm for computing ℳ_(w,k,ρ)(S) in 𝒪(n) time using 𝒪(√(w)) working space. We complement our theoretical results with a concrete application and an experimental evaluation.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections