In this paper, we present and study the Hamming distance oracle problem. In this problem, the task is to preprocess two strings S and T of lengths n and m, respectively, to obtain a data structure that is able to return the Hamming distance between a substring of S and a substring of T. For strings over a constant-size alphabet, we show that for every x ≤ min{n,m} there is a data structure with Õ(nm/x) preprocessing time and O(x) query time. We also provide a conditional lower bound, showing that for every ε > 0 there is no combinatorial data structure with query time O(x) and preprocessing time O((nm/x)^{1-ε}) unless combinatorial fast matrix multiplication is possible. For strings over a general alphabet, we present a data structure with Õ(nm/√x) pre-processing time and O(x) query time for every x ≤ min {n,m}. Moreover, for every ε > 0 we provide a data structure with a preprocessing time of Õ((n+m)/ε³) that returns with high probability a (1±ε) approximation of the Hamming distance of two input substrings. The query time of the approximation data structure is Õ(1/ε²).

We consider building, given a straight-line program (SLP) consisting of g productions deriving a two-dimensional string T of size N× N, a structure capable of providing random access to any character of T. For one-dimensional strings, it is now known how to build a structure of size 𝒪(g) that provides random access in 𝒪(log N) time. In fact, it is known that this can be obtained by building an equivalent SLP of size 𝒪(g) and depth 𝒪(log N) [Ganardi, Jeż, Lohrey, JACM 2021]. We consider the analogous question for two-dimensional strings: can we build an equivalent SLP of roughly the same size and small depth? We show that the answer is negative: there exists an infinite family of two-dimensional strings of size N× N described by a 2D SLP of size g such that any 2D SLP of depth 𝒪(log N) describing the same string must be of size Ω(g⋅ N/log³N). We complement this with an upper bound showing how to construct such a 2D SLP of size 𝒪(g⋅ N). Next, we observe that one can naturally define a generalization of 2D SLP, which we call 2D SLP with holes. We show that a known general balancing theorem by [Ganardi, Jeż, Lohrey, JACM 2021] immediately implies that, given a 2D SLP of size g deriving a string of size N× N, we can construct a 2D SLP with holes of depth 𝒪(log N) and size 𝒪(g). This allows us to conclude that there is a structure of size 𝒪(g) providing random access in 𝒪(log N) time for such a 2D SLP. Further, this can be extended (analogously as for a 1D SLP) to obtain a structure of size 𝒪(g log^ε N) providing random access in 𝒪(log N/log log N) time, for any ε > 0. The same (optimal) random access time was very recently achieved by [De and Kempa, SODA 2026], but with a significantly larger structure of size 𝒪(g log^{2+ε} N).

Hairpin completion, derived from the hairpin formation observed in DNA biochemistry, is an operation applied to strings, particularly useful in DNA computing. Conceptually, a right hairpin completion operation transforms a string $S$ into $S\cdot S'$ where $S'$ is the reverse complement of a prefix of $S$. Similarly, a left hairpin completion operation transforms a string $S$ into $S'\cdot S$ where $S'$ is the reverse complement of a suffix of $S$. The hairpin completion distance from $S$ to $T$ is the minimum number of hairpin completion operations needed to transform $S$ into $T$. Recently Boneh et al. showed an $O(n^2)$ time algorithm for finding the hairpin completion distance between two strings of length at most $n$. In this paper we show that for any $\varepsilon>0$ there is no $O(n^{2-\varepsilon})$-time algorithm for the hairpin completion distance problem unless the Strong Exponential Time Hypothesis (SETH) is false. Thus, under SETH, the time complexity of the hairpin completion distance problem is quadratic, up to sub-polynomial factors.

We study a natural type of repetitions in 2-dimensional strings. Such a repetition, called a matching frame, is a rectangular substring of size at least 2× 2 with equal marginal rows and equal marginal columns. Matching frames first appeared in literature in the context of Wang tiles. We present two algorithms finding a matching frame with the maximum perimeter in a given n× m input string. The first algorithm solves the problem exactly in Õ(n^{2.5}) time (assuming n ≥ m). The second algorithm finds a (1-ε)-approximate solution in Õ((nm)/ε⁴) time, which is near linear in the size of the input for constant ε. In particular, by setting ε = O(1) the second algorithm decides the existence of a matching frame in a given string in Õ(nm) time. Some technical elements and structural properties used in these algorithms can be of independent interest.

A $λ$-cover of a string $S$ is a set of strings $\{C_i\}_1^λ$ such that every index in $S$ is contained in an occurrence of at least one string $C_i$. The existence of a $1$-cover defines a well-known class of quasi-periodic strings. Quasi-periodicity can be decided in linear time, and all $1$-covers of a string can be reported in linear time plus the size of the output. Since in general it is NP-complete to decide whether a string has a $λ$-cover, the natural next step is the development of efficient algorithms for $2$-covers. Radoszewski and Straszyński [ESA 2020] analysed the particular case where the strings in a $2$-cover must be of the same length. They provided an algorithm that reports all such $2$-covers of $S$ in time near-linear in $|S|$ and in the size of the output. In this work, we consider $2$-covers in full generality. Since every length-$n$ string has $Ω(n^2)$ trivial $2$-covers (every prefix and suffix of total length at least $n$ constitute such a $2$-cover), we state the reporting problem as follows: given a string $S$ and a number $m$, report all $2$-covers $\{C_1,C_2\}$ of $S$ with length $|C_1|+|C_2|$ upper bounded by $m$. We present an $\tilde{O}(n + Output)$ time algorithm solving this problem, with Output being the size of the output. This algorithm admits a simpler modification that finds a $2$-cover of minimum length. We also provide an $\tilde{O}(n)$ time construction of a $2$-cover oracle which, given two substrings $C_1,C_2$ of $S$, reports in poly-logarithmic time whether $\{C_1,C_2\}$ is a $2$-cover of $S$.

Dynamic Time Warping (DTW) distance is the optimal cost of matching two strings when extending runs of letters is for free. Therefore, it is natural to measure the time complexity of DTW in terms of the number of runs n (rather than the string lengths N). In this paper, we give an Õ(n²) time algorithm for computing the DTW distance. This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest O(n³) time exact algorithm and the Õ(n²) time approximation algorithm. Our method also immediately implies an Õ(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n²k) and O(Nk) time exact algorithms and the Õ(nk) time approximation algorithm.

The $k$-mappability problem has two integers parameters $m$ and $k$. For every subword of size $m$ in a text $S$, we wish to report the number of indices in $S$ in which the word occurs with at most $k$ mismatches. The problem was lately tackled by Alzamel et al. For a text with constant alphabet $Σ$ and $k \in O(1)$, they present an algorithm with linear space and $O(n\log^{k+1}n)$ time. For the case in which $k = 1$ and a constant size alphabet, a faster algorithm with linear space and $O(n\log(n)\log\log(n))$ time was presented in a 2020 paper by Alzamel et al. In this work, we enhance the techniques of Alzamel et al.'s 2020 paper to obtain an algorithm with linear space and $O(n \log(n))$ time for $k = 1$. Our algorithm removes the constraint of the alphabet being of constant size. We also present linear algorithms for the case of $k=1$, $|Σ|\in O(1)$ and $m=Ω(\sqrt{n})$.

The recovery problem is the problem whose input is a corrupted text T that was originally periodic, and where one wishes to recover its original period. The algorithm’s input is T without any information about either the period’s length or the period itself. An algorithm that solves this problem is called a recovery algorithm. In order to make recovery possible, there must be some assumption that not "too many" errors corrupted the initial periodic string. This is called the error bound. In previous recovery algorithms, it was shown that a given error bound of n/((2+ε)p) can lead to O(log_{1+ε} n) period candidates, that are guaranteed to include the original period, where p is the length of the original period (unknown by the algorithm) and ε > 0 is an arbitrary constant. This paper provides the first analysis of the relationship between the error bound and the number of candidates, as well as identification of the error parameters that still guarantee recovery. We improve the previously known upper error bound on the number of corruptions, n/((2+ε)p), that outputs O(log_{1+ε} n) period candidates. We show how to (1) remove ε from the bound, (2) relax the error bound to allow more errors while keeping the candidates set of size O(log n). It turns out that this relaxation on the previously known upper bound is quite challenging. To achieve this result we provide what, to our knowledge, is the first known non-trivial lower bound on the Hamming distance between two periodic strings. This proof leads to an error bound, that produces a family of period candidates of size 2log₃ n. We show that this result is tight and further provide a compact representation of the period candidates. We call this representation the canonic period seed. In addition to providing less restrictive error bounds that guarantee a smaller candidate set, we also provide a hierarchy of more restrictive upper error bounds that asymptotically reduces the size of the potential period candidate set.

The Suffix Array SA(S) of a string S[1 … n] is an array containing all the suffixes of S sorted by lexicographic order. The suffix array is one of the most well known indexing data structures, and it functions as a key tool in many string algorithms. In this paper, we present a data structure for maintaining the Suffix Array of a dynamic string. For every 1 ≤ k ≤ n, our data structure reports SA[i] in 𝒪̃(n/k) time and handles text modification in 𝒪̃(k) time. Additionally, our data structure enables the same query time for reporting iSA[i], with iSA being the Inverse Suffix Array of S[1 … n]. Our data structure can be used to construct sub-linear dynamic variants of static strings algorithms or data structures that are based on the Suffix Array and the Inverse Suffix Array.

A string UU for a non-empty string U is called a square. Squares have been well-studied both from a combinatorial and an algorithmic perspective. In this paper, we are the first to consider the problem of maintaining a representation of the squares in a dynamic string S of length at most n. We present an algorithm that updates this representation in n^o(1) time. This representation allows us to report a longest square-substring of S in O(1) time and all square-substrings of S in O(output) time. We achieve this by introducing a novel tool - maintaining prefix-suffix matches of two dynamic strings. We extend the above result to address the problem of maintaining a representation of all runs (maximal repetitions) of the string. Runs are known to capture the periodic structure of a string, and, as an application, we show that our representation of runs allows us to efficiently answer periodicity queries for substrings of a dynamic string. These queries have proven useful in static pattern matching problems and our techniques have the potential of offering solutions to these problems in a dynamic text setting.

There has been recent interest in dynamic string algorithms, i.e. string problems where the input changes dynamically. One such problem is the longest common factor (LCF) problem. It is well known that the LCF of two strings S and D of length n over a fixed constant-sized alphabet Sigma can be computed in time linear in n. Recently, a new challenge was introduced - finding the LCF of two strings in a dynamic setting. The problem is the fully dynamic one sided LCF (FDOS-LCF) problem. In the FDOS-LCF problem we get q consecutive queries of the form , where each such query means: "replace D[i] by alpha, alpha in Sigma and output the LCF of S and (the updated) D. The goal is to initially preprocess S and D so that we do not need O(n) time to compute an LCF for each such query. The state-of-the-art is an algorithm that preprocesses the two strings S and D in time O(n log^4 n). Subsequently, the algorithm answers in time O(log^3 n) a single query of the form: Given a position i on D and a letter alpha, return an LCF of S and D', where D' is the string resulting from D after substituting D[i] with alpha. That algorithm is not extendable to multiple queries. In this paper we present a tool - Locally Maximal Common Factors (LMCF) - that proves to be quite useful in solving some restricted versions of the FDOS-LCF problem . The versions we solve are the Decremental FDOS-LCS problem, where every change is of the form , omega !in Sigma, and the Periodic FDOS-LCS problem, where S is a periodic string with period length p. For the decremental problem we provide an algorithm with linear time preprocessing and O(log log n) time per query. For the periodic problem our preprocessing time is linear and the query time is O(p log log n).