Minimizers in Semi-dynamic Strings

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 Σ. Further, let w≥2 and k≥1 be two integers and ρ=(Σ^k,≤) be a total order on Σ^k. 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 X based on ρ starts. The set of minimizers for all i∈[0,n-w-k+1] is the set M_w,k,ρ(S) of the minimizers of S. The set M_w,k,ρ(S) can be computed in O(n) time. The folklore algorithm computes the minimizer of every window in O(1) amortized time using O(w) working space. It is thus natural to pose the following two questions: Can we efficiently support other dynamic updates on the window?Can we improve on theO(w)working space? Can we efficiently support other dynamic updates on the window? Can we improve on theO(w)working space? We answer both questions in the affirmative: We term a string Xsemi-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 O(1) time with O(1) amortized time per update operation.We show that this data structure can be modified to occupy strongly sublinear space without increasing the time complexity of its operations. To the best of our knowledge, this yields the first algorithm for computing M_w,k,ρ(S) in O(n) time usingO(w)working space. We term a string Xsemi-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 O(1) time with O(1) amortized time per update operation. We show that this data structure can be modified to occupy strongly sublinear space without increasing the time complexity of its operations. To the best of our knowledge, this yields the first algorithm for computing M_w,k,ρ(S) in O(n) time usingO(w)working space.