The decades-old Pattern Matching with Edits problem, given a length-n string T (the text), a length-m string P (the pattern), and a positive integer k (the threshold), asks to list the k-error occurrences of P in T, that is, all fragments of T whose edit distance to P is at most k. The one-way communication complexity of this problem is the minimum number of bits that Alice, given an instance (P,T,k) of the problem, must send to Bob so that Bob can reconstruct the answer solely from that message. In recent work [STOC'24], we showed that, in the natural parameter regime 0 < k < m < n/2, Ω(n/m ⋅ k log(m/k)) bits are necessary and 𝒪(n/m ⋅ k log² m) bits are sufficient for this problem. More generally, for strings over an alphabet Σ, we gave an 𝒪(n/m ⋅ k log m log(m|Σ|))-bit encoding that allows one to recover a shortest sequence of edits for every k-error occurrence of P in T. In this paper, we revisit the original proof and improve the encoding size to 𝒪(n/m ⋅ k log (m|Σ|/k)), which matches the lower bound for constant-sized alphabets. We further establish a new tight lower bound of Ω(n/m ⋅ k log(m|Σ|/k)) for the edit sequence reporting variant we solve. Our encoding size also matches the communication complexity established for the simpler Pattern Matching with Mismatches problem in the context of streaming algorithms [Clifford, Kociumaka, Porat; SODA'19].

A Random Access query to a string T asks for the character T[i] at a given position i ∈ [0..|T|). This fundamental task admits a straightforward solution with constant-time queries and 𝒪(n log σ) bits of space when T ∈ [0..σ)ⁿ. While this is the best one can achieve in the worst case, much research has focused on the compressed setting: if T is compressible, one can hope for a much smaller data structure that still answers Random Access queries efficiently. In this work, we investigate the grammar-compressed setting, where T is represented by a context-free grammar that produces only T. Our main result is a general trade-off that optimizes Random Access time as a function of the string length n, the grammar size (the total length of productions) g, the alphabet size σ, the data structure size M, and the word size w ≥ Ω(log n) of the word RAM model. For any data structure size M satisfying glog n < Mw < nlog σ, we show an 𝒪(M)-size data structure that answers Random Access queries in time 𝒪(log((n log σ)/(Mw)) / log(Mw/(g log n))) . We also prove a matching unconditional lower bound that holds for all parameter regimes except very small grammars (g ≤ w^{1+o(1)} log n) and relatively small data structures (Mw ≤ g log n ⋅ w^o(1)). The lower bound applies to word-RAM query time and, more strongly, to the worst-case cell-probe complexity of nondeterministic or bounded-error randomized query algorithms. Previous work focused on optimizing the query time as a function of n only, achieving 𝒪(log n) time using 𝒪(g) space [Bille, Landau, Raman, Sadakane, Satti, Weimann; SIAM J. Comput. 2015] and 𝒪((log n)/(log log n)) time using 𝒪(g log^ε n) space for any constant ε > 0 [Belazzougui, Cording, Puglisi, Tabei; ESA 2015], [Ganardi, Jeż, Lohrey; J. ACM 2021]. Our result improves upon these bounds (strictly for g = n^{1-o(1)}) and generalizes them beyond M ≤ 𝒪(g poly log n), yielding a smooth interpolation with the uncompressed setting of Mw = nlogσ bits. Thus far, the only tight lower bound [Verbin and Yu; CPM 2013] was Ω((log n)/(log log n)) for w = Θ(log n), n^Ω(1) ≤ g ≤ n^{1-Ω(1), and M = g⋅log^Θ(1) n. In contrast, our result yields a tight bound that accounts for all relevant parameters and is valid for almost all parameter regimes. Our bounds remain valid for run-length grammars, where production sizes use run-length encoding. This lets us recover (and, for strings with small run-length grammars, improve) the trade-offs achieved by block trees, formulated in terms of the LZ77 size z [Belazzougui, Cáceres, Gagie, Gawrychowski, Kärkkäinen, Navarro, Ordóñez, Puglisi, Tabei; J. Comput. Syst. Sci. 2021] and substring complexity δ [Kociumaka, Navarro, Prezza; IEEE Trans. Inf. Theory 2023]. Our data structure admits an efficient deterministic construction algorithm. Beyond Random Access, its variants also support substring extraction (with optimal additive overhead 𝒪((m log σ)/w) for a length-m substring, provided that M ≥ g), as well as rank and select queries. All our results rely on novel grammar transformations that generalize contracting grammars [Ganardi; ESA 2021] and achieve the optimal trade-off between grammar size and height while enforcing extra structure crucial for constant-time navigation in the parse tree.

In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text \(T \in \Sigma^n\) while using space proportional to the size of \(T\) in compressed form. Nearly all fundamental queries can currently be efficiently supported in \(\mathcal{O}(\delta(T)\log^{\mathcal{O}(1)} n)\) space, where \(\delta(T)\) is the substring complexity—a strong compressibility measure that lower-bounds the optimal space required to represent the text [Kociumaka, Navarro, Prezza; IEEE Trans. Inf. Theory 2023]. In contrast, the optimal query time for compressed data structures has been characterized only for the basic random access problem.

We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array \(\mathrm{SA}_T[1..n]\) of a text \(T\) of length \(n\) encodes the lexicographic order of its suffixes and underlies numerous applications in pattern matching, data compression, and bioinformatics. Previous work established one-way reductions showing how suffix array queries can be answered using, for example, rank queries on the Burrows—Wheeler Transform. More recently, a new class of prefix queries was introduced, together with reductions that, among others, transform a simple tradeoff for prefix-select queries into a suffix array tradeoff matching state-of-the-art space and query-time bounds, while achieving sublinear construction time. For binary texts, the resulting data structure achieves space \(\mathcal{O}(n)\) bits, preprocessing time \(\mathcal{O}(n/\sqrt{\log n})\), preprocessing space \(\mathcal{O}(n)\) bits, and query time \(\mathcal{O}(\log^\epsilon n)\) for any constant \(\epsilon \gt 0\). However, whether these bounds could be improved using different techniques has remained open.

A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length \(n\)) into an efficient index (a data structure) supporting queries about the text. While the most fundamental exact pattern matching queries ask to find all the occurrences of a pattern (a string of length \(m\)) as substrings of the text, many applications call for approximate pattern matching queries, where the pattern may differ slightly from the matching substrings. A breakthrough in the extensive study of approximate text indexing came from Cole, Gottlieb, and Lewenstein (STOC 2004), who proposed \(k\)-errata trees — a family of text indexes supporting several closely related flavors of approximate pattern matching queries. In particular, \(k\)-errata trees yield an elegant solution to \(k\)-mismatch queries, where the similarity is quantified using an upper bound \(k \ge 1\) on the Hamming distance between the pattern and its approximate occurrences. The resulting \(k\)-mismatch index uses \(\mathcal{O}(n \log^{k} n)\) space and answers a query for a length-\(m\) pattern in \(\mathcal{O}(\log^{k} n \log \log n + m + \texttt{occ})\) time, where \(\texttt{occ}\) is the number of approximate occurrences.

A powerful design principle behind many modern string algorithms is local consistency: breaking the symmetry between string positions based on their small contexts so that matching fragments are handled consistently. Among the most influential instantiations of this principle are string synchronizing sets [Kempa & Kociumaka; STOC 2019]. A τ-synchronizing set of a string of length n is a set of O(n/τ) string positions, chosen using their length-2τ contexts, such that (outside of highly periodic regions) every block of τ consecutive positions contains at least one element of the set. Synchronizing sets have found dozens of applications in diverse settings, from quantum and dynamic algorithms to fully compressed computation. In the classic word RAM model, particularly for strings over small alphabets, they enabled faster solutions to core problems in data compression, text indexing, and string similarity. In this work, we show that any string T ∈ [0 .. σ)ⁿ can be preprocessed in O(n log σ / log n) time so that, for any given integer τ ∈ [1 .. n], a τ-synchronizing set of T can be constructed in O((n log τ)/(τ log n)) time. Both bounds are optimal in the word RAM model with machine word size w = Θ(log n), matching the information-theoretic minimum for the input and output sizes, respectively. Previously, constructing a τ-synchronizing set required O(n/τ) time after an O(n)-time preprocessing [Kociumaka, Radoszewski, Rytter, and Waleń; SICOMP 2024], or, in the restricted regime of τ < 0.2 log_σ n, without any preprocessing needed [Kempa & Kociumaka; STOC 2019]. A simple instantiation of our method outputs the synchronizing set as a sorted list in O(n/τ) time, or as a bitmask in O(n/log n) time. Our optimal construction produces a compact fully indexable dictionary, supporting select queries in O(1) time and rank queries in O(log ((log τ)/(log log n))) time. The latter complexity matches known unconditional cell-probe lower bounds for τ ≤ n^{1-Ω(1)}. To achieve this, we introduce a general framework for efficiently processing sparse integer sequences via a custom variable-length encoding. We also augment the optimal variant of van Emde Boas trees [Pătraşcu & Thorup; STOC 2006] with a deterministic linear-time construction. When the set is represented as a bitmask under our sparse encoding, the same guarantees for select and rank queries hold after preprocessing in time proportional to the size of our encoding (in words).

Abstract We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is $$\textsf {NP}$$ NP -hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} \log (n))$$ O ( log ( opt ) log ( n ) ) . An important aspect of our work – that is relevant in its own right and of independent interest – is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature and are arguably among the most central graph parameters that are based on “linearisations” of graphs. In this way, we also identify a direct approximation preserving reduction from cutwidth to pathwidth, which shows that any polynomial $$f({{\,\mathrm{\textsf {opt}}\,}},|V|)$$ f ( opt , | V | ) -approximation algorithm for pathwidth yields a polynomial $$2f(2{{\,\mathrm{\textsf {opt}}\,}},h)$$ 2 f ( 2 opt , h ) -approximation algorithm for cutwidth on multigraphs (where h is the number of edges). In particular, this translates known approximation ratios for pathwidth into new approximation ratios for cutwidth, namely $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} \log (h))$$ O ( log ( opt ) log ( h ) ) and $${{\,\textrm{O}\,}}(\sqrt{\log ({{\,\mathrm{\textsf {opt}}\,}})} {{\,\mathrm{\textsf {opt}}\,}})$$ O ( log ( opt ) opt ) for (multi) graphs with h edges.

Co-lex partial orders (Cotumaccio et al., SODA 2021 and Journal of the ACM 2023) are a powerful tool to index finite automata, with applications to regular expression matching, generalizing Wheeler orders (Gagie et al., Theoretical Computer Science 2017). The co-lex width p of an automaton naturally measures how sortable its states are w.r.t. the co-lexicographic order among its accepted strings. Automata of co-lex width p can be compressed to O ( log ⁡ p ) bits per edge and admit regular expression matching in time proportional to p 2 per matched character. The deterministic co-lex width of a regular language L is the smallest width of such a co-lex order, among all DFAs recognizing L . Since languages of small co-lex width admit efficient solutions to hard computational problems on the language, computing the co-lex width of a language is relevant in applications. Previous work shows that the deterministic co-lex width p of a language L can be computed in m O ( p ) , given as input any DFA A with m transitions accepting L . For constant p (in particular Wheeler languages, where p = 1 ), the constant in the exponent is large and the exact complexity remains unknown. In this work, using new techniques, we show that one can decide in O ( m p ) if the deterministic co-lex width of the language recognized by a given minimum DFA is strictly smaller than p ≥ 2 . We complement this with a matching conditional lower bound based on the Strong Exponential Time Hypothesis. Hence, our paper essentially settles the complexity of the problem.

Abstract Internal Pattern Matching (IPM) queries on a length- $$n$$ n text T , given two fragments X and Y of T such that $$|Y|<2|X|$$ | Y | < 2 | X | , ask to compute all exact occurrences of X within Y . IPM queries have been introduced by Kociumaka, Radoszewski, Rytter, and Waleń [SODA’15 & SICOMP’24], who showed that they can be answered in $$\mathcal {O}(1)$$ O ( 1 ) time using a data structure of size $$\mathcal {O}(n)$$ O ( n ) and used this result to answer various queries about fragments of T . In this work, we study IPM queries on compressed and dynamic strings. Our result is an $$\mathcal {O}(\log n)$$ O ( log n ) -time query algorithm applicable to any balanced recompression-based run-length straight-line program (RLSLP). In particular, one can use it on top of the RLSLP of Kociumaka, Navarro, and Prezza [IEEE TIT’23], whose size $$\mathcal {O}\big (\delta \log \frac{n\log \sigma }{\delta \log n}\big )$$ O ( δ log n log σ δ log n ) is optimal (among all text representations) as a function of the text length n , the alphabet size $$\sigma $$ σ , and the substring complexity $$\delta $$ δ . Our procedure does not rely on any preprocessing of the underlying RLSLP, which makes it readily applicable on top of the dynamic strings data structure of Gawrychowski, Karczmarz, Kociumaka, Łącki and Sankowski [SODA’18], which supports fully persistent updates in logarithmic time with high probability.

In the classic Longest Common Substring (LCS) problem, we are given two strings $S$ and $T$ of total length $n$, over an alphabet of size $\sigma$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. Weiner, in his seminal paper that introduced the suffix tree, presented an $\mathcal{O}(n \log \sigma)$-time algorithm for this problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an $\mathcal{O}(n)$-time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in $\mathcal{O}(n \log \sigma/\log n )$ space and read in $\mathcal{O}(n \log \sigma/\log n )$ time. We show that we can compute an LCS of two strings in time $\mathcal{O}(n \log \sigma / \sqrt{\log n})$ in the word RAM model, which is sublinear in $n$ if $\sigma=2^{o(\sqrt{\log n})}$ (in particular, if $\sigma=\mathcal{O}(1)$), using optimal space $\mathcal{O}(n \log \sigma/\log n)$. In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. The same complexity can be achieved for computing an LCS of $\lambda = \mathcal{O}(\sqrt{\log n}) / \log {\log n})$ input strings of total length $n$. We then lift our ideas to the problem of computing a $k$-mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of $S$ that occurs in $T$ with at most $k$ mismatches. Flouri et al. showed how to compute a 1-mismatch LCS in $\mathcal{O}(n \log n)$ time [IPL 2015]. Thankachan et al. showed how to computing a $k$-mismatch LCS in $\mathcal{O}(n \log^k n)$ time for $k=\mathcal{O}(1)$ [J. Comput. Biol. 2016]. We show an $\mathcal{O}(n \log^{k-0.5} n)$-time algorithm, for any constant $k>0$ and irrespective of the alphabet size, using $\mathcal{O}(n)$ space as the previous approaches. We thus notably break through the well-known $n \log^k n$ barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. [STOC 2004] for string indexing with $k$ errors [STOC 2004].

In Pattern Matching with Weighted Edits (PMwWE), we are given a pattern P of length m, a text T of length n, a positive threshold k, and oracle access to a weight function that specifies the costs of edits (depending on the involved characters, and normalized so that the cost of each edit is at least 1). The goal is to compute the starting positions of all fragments of T that can be obtained from P with edits of total cost at most k. PMwWE captures typical real-world applications more accurately than its unweighted variant (PMwE), where all edits have unit costs.Indeed, the textbook $\mathcal{O}\left( {nm} \right)$-time algorithm of Sellers [J. Algorithms'80], devised in the context of bioinformatics, already accounts for weights. Surprisingly, the understanding of PMWWE has not advanced in the last 45 years. In contrast, significant milestones for PMwE include an $\mathcal{O}\left( {nk} \right)$-time algorithm by Landau and Vishkin [STOC'86, J. Algorithms'89], an $\mathcal{O}(n + {k^4} \cdot n/m)$-time algorithm by Cole and Hariharan [SODA'98, SICOMP'02], and a recent $\tilde {\mathcal{O}}(n + {k^{3.5}} \cdot n/m)$-time solution by Charalampopoulos, Kociumaka, and Wellnitz [FOCS'22].In this work, we examine whether these results can be lifted to PMWWE even though (1) the underlying algorithms rely on combinatorial properties specific to the unweighted edit distance, and (2) under standard fine-grained complexity assumptions, computing the weighted edit distance is strictly harder than computing the unweighted edit distance [Cassis, Kociumaka, and Wellnitz; FOCS'23]. We obtain three main results:•a conceptually simple $\tilde {\mathcal{O}}\left( {nk} \right)$-time algorithm for PMWWE, very different from that of Landau and Vishkin;•a significantly more complicated $\tilde {\mathcal{O}}(n + {k^{3.5}} \cdot {W^4} \cdot n/m)$ time algorithm for PMWWE under the assumption that the weight function is a metric with integer values between 0 and W; and•an $\tilde {\mathcal{O}}(n + {k^4} \cdot n/m)$-time algorithm for PMWWE for the case of arbitrary weights. In the setting of metrics with small integer values, we nearly match the state of the art for PMwE where W=1.

In this paper, we present the first dynamic algorithms for Dyck edit distance and tree edit distance that achieve subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a wellparenthesized expression (i.e., the Dyck language), while tree edit distance quantifies the minimum number of node insertions, deletions, and substitutions required to transform one rooted, ordered, and labeled tree into another. These problems have been studied extensively since the 1970s, with recent advances in both algorithmic efficiency and fine-grained complexity lower bounds. Despite this progress, no prior work has addressed efficient dynamic algorithms for these problems, even though many real-world applications involve evolving structured data such as LaTeX, JSON, XML, HTML, hierarchical datasets, and RNA secondary structures. We take the first step in this direction by designing new approximation algorithms for Dyck and tree edit distances in the dynamic setting. Our key technical contribution is a set of novel reduction and decomposition techniques that transform instances of Dyck and tree edit distance into efficiently maintainable instances of string edit distance. Leveraging existing dynamic algorithms for string edit distance, we obtain an $n^{o(1)}$ approximation for Dyck edit distance with $n^{o(1)}$ update time. This builds upon and significantly extends prior work on Dyck language decomposition ([Saha, FOCS’14] and [Koucký & Saks; SODA’23]). For tree edit distance, we introduce a new static reduction that improves the best-known approximation bound from $O\left(n^{3 / 4}\right)$ [Akutsu, Fukagawa, and Takasu; Algorithmica, 2010] to $\tilde{O}(\sqrt{n})$. Moreover, while the previous result was restricted to constant-degree trees, ours holds for arbitrary trees. We then extend our reduction dynamically, yielding a dynamic tree edit distance algorithm with an approximation factor of $n^{1 / 2+o(1)}$ and update time $n^{o(1)}$. A core component of our approach is a new dynamic maintenance algorithm for heavy-light decomposition, a widely used technique in tree algorithms. Given its broad applicability, we believe this result is of independent interest. Finally, we introduce a novel static and dynamic decomposition method that achieves an $\tilde{O}(k)$-approximation for tree edit distance when the tree edit distance is at most k; combined with the trivial bound $k \leq n$, this yields a deterministic $\tilde{O}(\sqrt{n})$-approximation. While similar decompositions exist for strings, no prior work has successfully extended them to trees. Our approach breaks this barrier, improving the best-known approximations for tree edit distance both in the static and dynamic setting. In the static setting, our algorithm runs in $\tilde{O}(n)$ time; in the dynamic setting, it only requires a polylogarithmic worst-case update time. The state-of-the-art near-lineartime static algorithm for tree edit distance previously achieved an $O(\sqrt{n})$-approximation [Boroujeni, Ghodsi, Hajiaghayi, and Seddighin; STOC’19].

The classic exact pattern matching problem, given two strings——a pattern P of length m and a text T of length n—— asks whether P occurs as a substring of T, that is, $P= T[i. . i+m)$ holds for some $i \in[0. . n-m]$. A property tester for the problem needs to distinguish (with high probability) the following two cases for some threshold $k \in[1. . m)$: the Yes case, where P occurs as a substring of T, and the No case, where $\boldsymbol{P}$ has Hamming distance greater than k from every substring of T, that is, P has no k-mismatch occurrence in T. In this work, we provide adaptive and non-adaptive property testers for the exact pattern matching problem, jointly covering the whole spectrum of parameters. We further establish unconditional lower bounds demonstrating that the time and query complexities of our algorithms are optimal, up to polylog n factors hidden within the $\widetilde{\mathcal{O}}(\cdot)$ notation below. In the most studied regime of $n=m+\Theta(m)$, our nonadaptive property tester has the time complexity of $\widetilde{\mathcal{O}}(n / \sqrt{k})$, and a matching lower bound remains valid for the query complexity of adaptive algorithms. This improves both upon a folklore solution that attains the optimal query complexity but requires $\Omega(n)$ time, and upon the only previously known sublineartime property tester, by Chan, Golan, Kociumaka, Kopelowitz, and Porat [STOC 2020], with time complexity $\widetilde{\mathcal{O}}(n / \sqrt[3]{k})$. The aforementioned results remain valid for $n=m+\Omega(m)$, where our optimal running time $\widetilde{\mathcal{O}}(\sqrt{n m / k}+n / k)$ improves upon the previously best time complexity of $\mathcal{O}\left(\sqrt[3]{n^{2} m / k}+n / k\right)$. In the regime of $n=m+o(m)$, which has not been targeted in any previous work, we establish a surprising separation between adaptive and non-adaptive algorithms, whose optimal time and query complexities are $\widetilde{\mathcal{O}}(\sqrt{(n-m+1) m / k}+n / k)$ and $\widetilde{\mathcal{O}}(\min (n \sqrt{n-m+1} / k, \sqrt{n m / k}+n / k))$, respectively. Our non-adaptive algorithms answer Yes with high probability not only when P has an exact occurrence in T but also when P has an occurrence with at most $k^{\prime}=\Omega(k / \log n)$ mismatches. The gap $k / k^{\prime}$ can be reduced by slightly increasing the running time; an arbitrarily small polynomial overhead already suffices to achieve a constant gap. Moreover, upon request, our algorithms may output a set $A \subseteq[0. . n-m]$ that contains the starting positions of all $\boldsymbol{k}^{\prime}$-mismatch occurrences of $\boldsymbol{P}$ in $\boldsymbol{T}$ and no starting position of an occurrence with more than k mismatches. The key technical innovation behind all our property testers is a novel characterization of the mismatches between the pattern P and the fragments $T[i . . i+m)$ across $i \in[0. . n-m]$. We show that one can select $\widetilde{\mathcal{O}}(k \cdot n / m)$ positions within P and T so that, for every $i \in[0. . n-m]$, at least $\min \left(k, k_{i}\right)$ of the $k_{i}$ mismatches between P and $T[i .. i+m)$ involve a selected position. Previously, such a construction was known for k

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to identify the fragments of T that are at distance at most k to P. We consider the two most common distances: Hamming distance (the number of mismatches or character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting.

In this work, we study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms that take $O(n\sqrt{\log n})$ time for instances described in $Θ(n)$ machine words ($Θ(n\log n)$ bits). This complexity class, one of six hardness levels identified by Chan and Pătraşcu [SODA 2010], includes diverse problems from several domains: Counting Inversions, string processing problems (BWT Construction, LZ77 Factorization, Longest Common Substring, Batched Longest Previous Factor Queries, Batched Inverse Suffix Array Queries), and computational geometry tasks (Orthogonal Range Counting, Orthogonal Segment Intersection). We offer two main contributions: We establish new links between the above string problems and Dictionary Matching, a classic task solvable using the Aho-Corasick automaton. We restrict Dictionary Matching to instances with $O(n)$ binary patterns of length $m = O(\log n)$ each, and we prove that, unless these instances can be solved in $o(n\sqrt{\log n})$ time, the aforementioned string problems cannot be solved faster either. Via further reductions, we extend this hardness to Counting Inversions (a fundamental component in geometric algorithms) and thus to Orthogonal Range Counting and Orthogonal Segment Intersection. This hinges on String Nesting, a new problem which is equivalent to Dictionary Matching and can be reduced to Counting Inversions in three steps. Together, our results unveil a single problem, with two equivalent formulations, that underlies the hardness of nearly all major problems currently occupying the $O(n\sqrt{\log n})$ level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. As an auxiliary outcome of our framework, we also prove that the alphabet in several central string problems can be efficiently reduced to binary.

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string$T$from left to right into blocks (called phrases) so that each phrase is either the leftmost occurrence of a single letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in the text. This simple routine has numerous applications. Most importantly, the LZ77 factorization is the central component and the computational bottleneck of most existing compression algorithms (utilized in formats like zip, pdf, and png). LZ77 is also a widely used algorithmic tool for the detection of repetitions and periodicities in strings, and the centerpiece of many powerful compressed indexes that enable computation directly over compressed data. LZ77 factorization is one of the most studied problems in string processing. In the 47 years since its inception, numerous efficient algorithms were developed for different models of computation, including parallel, GPU, external-memory, and quantum. Remarkably, however, the complexity of the most basic problem is still not settled: All existing algorithms in the RAM model run in$\Omega(n)$time, which is a$\Theta(\log n)$factor away from the lower bound of$\Omega(n/\log n)$(following simply from the necessity to read the entire input, which takes$\Theta(n/\log n)$space for any$T\in\{0,1\}^{n})$. Sublinear-time algorithms are known for nearly all other fundamental problems on strings, but LZ77 seems resistant to all currently known techniques. We present the first$o(n)$-time algorithm for constructing the LZ77 factorization, breaking the linear-time barrier present for nearly 50 years. More precisely, we show that, in the standard RAM model, it is possible to compute the LZ77 factorization of a given length-$n$string$T\in \{0,1\}^{n}$in$\mathcal{O}(n/\sqrt{\log n})=o(n)$time and using the optimal$O(n/\log n)$working space. Our algorithm generalizes to larger alphabets$\Sigma=[0.. \sigma),\text{ where }\sigma=n^{\mathcal{O}2(1)}$. The runtime and working space then become$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$and$\mathcal{O}(n/\log_{\sigma}n)$, respectively. To achieve this sublinear-time LZ77 algorithm, we prove a more general result: We show that, for any constant$\epsilon\in(0,1)$and string$T\in[0..\sigma)^{n}$, in$\mathcal{O}((n\log\sigma)/\sqrt{\log n})$time and using$\mathcal{O}(n/\log_{\sigma}n)$working space, we can construct an index of optimal size$\mathcal{O}(n/\log_{\sigma}n)$that, given any substring$P=T[j.. j+\ell)$specified with a pair$(j,\ell)$, computes the leftmost occurrence of$P$in$T$in$O(\log^{\epsilon}n)$time. In other words, we solve the indexing/online variant of the LZ77 problem, where we can efficiently query the phrase length starting at any position. Our solution is based on a new type of queries that we call prefix range minimum queries or prefix RMQ. After developing an efficient solution for these queries, we provide a general reduction showing that any new tradeoff for the prefix RMQ implies a new tradeoff for an index finding leftmost occurrences (and hence a new LZ77 factorization algorithm).

We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable shift in focus towards sublinear-time algorithms. Here, the task is typically formalized as the (k, K)-gap edit distance problem: Distinguish whether the edit distance of two strings is at most k or more than K.

The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensitive alternative to the Fréchet distance. For static curves of at most n points, the DTW distance can be computed in O(n2) time in constant dimension. This tightly matches a SETH-based lower bound, even for curves in ℝ1.

Measuring sequence similarity and compressing texts are among the most fundamental tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the central problems in these two areas: computing the edit distance of two strings [Levenshtein, 1965] and building the Lempel-Ziv factorization of a string [Ziv & Lempel, 1977], respectively.

In the Massively Parallel Computation (MPC) model, data is distributed across multiple processors, and we call an algorithm space-efficient if each machine has n^1-ε + o(1) memory with a machine count of Ømega(n^ε).

The decades-old Pattern Matching with Edits problem, given a length-n string T (the text), a length-m string P (the pattern), and a positive integer k (the threshold), asks to list all fragments of T that are at edit distance at most k from P. The one-way communication complexity of this problem is the minimum amount of space needed to encode the answer so that it can be retrieved without accessing the input strings P and T.

Abstract Given a string T of length n whose characters are drawn from an ordered alphabet of size $$\sigma $$ σ , its longest Lyndon subsequence is a maximum-length subsequence of T that is a Lyndon word. We propose algorithms for finding such a subsequence in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$ O ( n 3 ) time with $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n)$$ O ( n ) space, or online in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^3)$$ O ( n 3 ) space and time. Our first result can be extended to find the longest common Lyndon subsequence of two strings of length at most n in $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^4 \sigma )$$ O ( n 4 σ ) time using $$\mathop {}\mathopen {}\mathcal {O}\mathopen {}(n^2)$$ O ( n 2 ) space.

Abstract. We consider several types of internal queries, that is, questions about fragments of a given text [Formula: see text] specified in constant space by their locations in [Formula: see text]. Our main result is an optimal data structure for internal pattern matching (IPM) queries, which, given two fragments [Formula: see text] and [Formula: see text], ask for a representation of all fragments contained in [Formula: see text] and matching [Formula: see text] exactly. This problem can be viewed as an internal version of the fundamental exact pattern matching problem: We are looking for exact occurrences of one substring of [Formula: see text] within another substring of [Formula: see text]. Our data structure answers IPM queries in time proportional to the quotient [Formula: see text] of the fragments’ lengths, which is required due to the worst-case information content of the output. If [Formula: see text] is a text of length [Formula: see text] over an integer alphabet of size [Formula: see text], then our data structure occupies [Formula: see text] machine words (that is, [Formula: see text] bits) and admits an [Formula: see text]-time construction algorithm. We also show how to use IPM queries for answering internal queries corresponding to other classic string processing problems. Among others, we derive optimal data structures reporting the periods of a fragment and testing the cyclic equivalence of two fragments. Since the publication of the conference version of this paper [Kociumaka et al., Internal pattern matching queries in a text and applications, SODA 2015], IPM queries have found numerous further applications, following the path paved by the classic longest common extension (LCE) queries of Landau and Vishkin [ J. Comput. System Sci., 37 (1988), pp. 63–78]. In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the [Formula: see text] model, developed by Charalampopoulos, Kociumaka, and Wellnitz [ Faster approximate pattern matching: A unified approach, FOCS 2020] to design approximate pattern matching algorithms that work in multiple settings. All our algorithms are deterministic, whereas the data structure in the conference version of the paper only admits a randomized construction in [Formula: see text] expected time. To achieve this, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka [ String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure, STOC 2019]. Our method, based on a new restricted version of the recompression technique of Jeż [ J. ACM, 63 (2016), pp. 4:1–4:51], yields a hierarchy of [Formula: see text] string synchronizing sets covering the whole spectrum of the fragments’ lengths.

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform S into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses S and a positive integer k , and the goal is to compute the Dyck edit distance of S only if the distance is at most k , and otherwise report that the distance is larger than k . Backurs and Onak [PODS’16] showed that the threshold Dyck edit distance problem can be solved in O ( n + k 16 ) time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs O ( n + k 4.544184 ) time with high probability or O ( n + k 4.853059 ) deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant’s parsing algorithm.

In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wulff-Nilsen established a near-linear $O(m \log^8(n) \log(W))$-time algorithm for negative-weight SSSP, where $W$ is an upper bound on the magnitude of the smallest negative-weight edge. In this work we improve the running time to $O(m \log^2(n) \log(nW) \log\log n)$, which is an improvement by nearly six log-factors. Some of these log-factors are easy to shave (e.g. replacing the priority queue used in Dijkstra's algorithm), while others are significantly more involved (e.g. to find negative cycles we design an algorithm reminiscent of noisy binary search and analyze it with drift analysis). As side results, we obtain an algorithm to compute the minimum cycle mean in the same running time as well as a new construction for computing Low-Diameter Decompositions in directed graphs.

The edit distance (also known as Levenshtein distance) of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic-programming algorithm computes the edit distance of two length- n strings in $\mathcal{O}\left(n^{2}\right)$ time, which is optimal up to subpolynomial factors assuming the Strong Exponential Time Hypothesis (SETH). An established way of circumventing this hardness is to consider the bounded setting, where the running time is parameterized by the edit distance k. A celebrated algorithm by Landau and Vishkin (JCSS’88) achieves a running time of $\mathcal{O}\left(n+k^{2}\right)$, which is optimal as a function of n and k (again, up to subpolynmial factors and assuming SETH).While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet $\Sigma$. This is formalized through a weight function $w: \Sigma \cup\{\varepsilon\} \times \Sigma \cup\{\varepsilon\} \rightarrow \mathbb{R}$ normalized so that $w(a \mapsto a)=0$ for $a \in \Sigma \cup\{\varepsilon\}$ and $w(a \mapsto b) \geq 1$ for $a, b \in \Sigma \cup\{\varepsilon\}$ with $a \neq b$; the goal is to find an alignment of the two strings minimizing the total weight of edits. The classic $\mathcal{O}\left(n^{2}\right)$-time algorithm supports this setting seamlessly, but for many decades just a straightforward $\mathcal{O}(n k)$-time solution was known for the bounded version of the weighted edit distance problem. Only very recently, Das, Gilbert, Hajiaghayi, Kociumaka, and Saha (STOC’23) gave the first non-trivial algorithm, achieving a time complexity of $\mathcal{O}\left(n+k^{5}\right)$. While this running time is linear for $k \leq n^{1 / 5}$, it is still very far from $\mathcal{O}\left(n+k^{2}\right)$-the bound achievable in the unweighted setting. This is unsatisfactory, especially given the lack of any compelling evidence that the weighted version is inherently harder.In this paper, we essentially close this gap by showing both an improved $\widetilde{\mathcal{O}}\left(n+\sqrt{n k^{3}}\right)$-time algorithm and, more surprisingly, a matching lower bound: Conditioned on the All-Pairs Shortest Paths (APSP) hypothesis, the running time of our solution is optimal for $\sqrt{n} \leq k \leq n$ (up to subpolynomial factors). In particular, this is the first separation between the complexity of the weighted and unweighted edit distance problems.Just like the Landau-Vishkin algorithm, our algorithm can be adapted to a wide variety of settings, such as when the input is given in a compressed representation. This is because, independently of the string length n, our procedure takes $\widetilde{\mathcal{O}}\left(k^{3}\right)$ time assuming that the equality of any two substrings can be tested in $\widetilde{\mathcal{O}}(1)$ time.Consistently with the previous work, our algorithm relies on the observation that strings with a rich structure of low-weight alignments must contain highly repetitive substrings. Nevertheless, achieving the optimal running time requires multiple new insights. We capture the right notion of repetitiveness using a tailor-made compressibility measure that we call self-edit distance. Our divide-and-conquer algorithm reduces the computation of weighted edit distance to several subproblems involving substrings of small self-edit distance and, at the same time, distributes the budget for edit weights among these subproblems. We then exploit the repetitive structure of the underlying substrings using state-of-the-art results for multiple-source shortest paths in planar graphs (Klein, SODA’05).As a stepping stone for our conditional lower bound, we study a dynamic problem of maintaining two strings subject to updates (substitutions of characters) and weighted edit distance queries. We significantly extend the construction of Abboud and Dahlgaard (FOCS’16), originally for dynamic shortest paths in planar graphs, to show that a sequence of n updates and $q \leq n$ queries cannot be handled much faster than in $\mathcal{O}\left(n^{2} \sqrt{q}\right)$ time. We then compose the snapshots of the dynamic strings to derive hardness of the static problem in the bounded setting.

The last two decades have witnessed a dramatic increase in the amount of highly repetitive datasets consisting of sequential data (strings, texts). Processing these massive amounts of data using conventional data structures is infeasible. This fueled the development of compressed text indexes, which efficiently answer various queries on a given text, typically in polylogarithmic time, while occupying space proportional to the compressed representation of the text. There exist numerous structures supporting queries ranging from simple “local” queries, such as random access, through more complex ones, including longest common extension (LCE) queries, to the most powerful queries, such as the suffix array (SA) functionality. Alongside the rich repertoire of queries followed a detailed study of the trade-off between the size and functionality of compressed indexes (see: Navarro; ACM Comput. Surv. 2021). It is widely accepted that this hierarchy of structures tells a simple story: the more powerful the queries, the more space is needed. On the one hand, random access, the most basic query, can be supported using $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space (where n is the length of the text, $\sigma$ is the alphabet size, and $\delta$ is the text’s substring complexity), which is known to be the asymptotically smallest space sufficient to represent any string with parameters $n, \sigma$, and $\delta$ (Kociumaka, Navarro, and Prezza; IEEE Trans. Inf. Theory 2023). The other end of the hierarchy is occupied by indexes supporting the suffix array queries. The currently smallest one takes $\mathcal{O}\left(r \log \frac{n}{r}\right)$ space, where $r \geq \delta$ is the number of runs in the Burrows-Wheeler Transform of the text (Gagie, Navarro, and Prezza; J. ACM 2020). We present a new compressed index, referred to as $\delta$ SA, that supports the powerful SA functionality and needs only $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space. This collapses the hierarchy of compressed data structures into a single point: The space required to represent the text is simultaneously sufficient to efficiently support the full SA functionality. Since suffix array queries are the most widely utilized queries in string processing and data compression, our result immediately improves the space complexity of dozens of algorithms, which can now be executed in $\delta$-optimal compressed space. The $\delta$-SA supports both suffix array and inverse suffix array queries in $\mathcal{O}\left(\log ^{4+\epsilon} n\right)$ time (where $\epsilon \gt 0$ is any predefined constant). Our second main result is an $\mathcal{O}(\delta$ polylog $n)$-time construction of the $\delta$-SA from the Lempel-Ziv (LZ77) parsing of the text. This is the first algorithm that builds an SA index in compressed time, i.e., time nearly linear in the compressed input size. For highly repetitive texts, this is up to exponentially faster than the previously best algorithm, which builds an $\mathcal{O}\left(r \log \frac{n}{r}\right)$-size index in $\mathcal{O}(\sqrt{\delta n}$ polylog $n)$ time. To obtain our results, we develop numerous new techniques of independent interest. This includes deterministic restricted recompression, $\delta$-compressed string synchronizing sets, and their construction in compressed time. We also improve many other auxiliary data structures; e.g., we show the first $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$-size index for LCE queries along with its efficient construction from the LZ77 parsing.

The edit distance is a fundamental measure of sequence similarity, defined as the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. Given two strings of length at most n, a simple dynamic programming computes their edit distance exactly in $\mathcal{O}\left(n^{2}\right)$ time, which is also the best possible (up to subpolynomial factors) assuming the Strong Exponential Time Hypothesis (SETH). The last few decades have seen tremendous progress in edit distance approximation, where the runtime has been brought down to subquadratic, to near-linear, and even to sublinear at the cost of approximation. In this paper, we study the dynamic edit distance problem where the strings change dynamically as the characters are substituted, inserted, or deleted over time. Each change may happen at any location of either of the two strings. The goal is to maintain the (exact or approximate) edit distance of such dynamic strings while minimizing the update time. The exact edit distance can be maintained in $\mathcal{O}\left(n \log ^{2} n\right)$ time per update (Charalampopoulos, Kociumaka, Mozes; 2020), which is again tight assuming SETH. Unfortunately, even with the unprecedented progress in edit distance approximation in the static setting, strikingly little is known regarding dynamic edit distance approximation. Utilizing the best near-linear-time (Andoni, Nosatzki; 2020) and sublinear-time (Goldenberg, Kociumaka, Krauthgamer, Saha; 2022) approximation algorithm, an old exact algorithm (Landau and Vishkin; 1988), and a generic dynamic strings implementation (Mehlhorn, Sundar, Uhrig; 1996), it is possible to achieve an $\mathcal{O}\left(n^{c}\right)$-approximation in $n^{0.5-c+o(1)}$ update time for any constant $c \in\left[0, \frac{1}{6}\right]$. Improving upon this trade-off, characterized by the approximation-ratio and update-time product $n^{0.5+o(1)}$, remains wide open. The contribution of this work is a dynamic $n^{o(1)}$-approximation algorithm with amortized expected update time of $n^{o(1)}$. In other words, we bring the approximation-ratio and update-time product down to $n^{o(1)}$, which is also the best possible with the current state of the art in static algorithms. Our solution utilizes an elegant framework of precision sampling trees for edit distance approximation (Andoni, Krauthgamer, Onak; 2010). We show how to dynamically maintain precision sampling trees, which comes with significant nontriviality and can be an independent tool of interest for further development in dynamic string algorithms.

The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In many real-life scenarios, insertions and deletions (abbreviated indels) appear frequently but significantly less so than substitutions. To model this, we consider substitutions being cheaper than indels, with cost $1/a$ for a parameter $a\ge 1$. This basic variant, denoted $ED_a$, bridges classical edit distance ($a=1$) with Hamming distance ($a\to\infty$), leading to interesting algorithmic challenges: Does the time complexity of computing $ED_a$ interpolate between that of Hamming distance (linear time) and edit distance (quadratic time)? What about approximating $ED_a$? We first present a simple deterministic exact algorithm for $ED_a$ and further prove that it is near-optimal assuming the Orthogonal Vectors Conjecture. Our main result is a randomized algorithm computing a $(1+ε)$-approximation of $ED_a(X,Y)$, given strings $X,Y$ of total length $n$ and a bound $k\ge ED_a(X,Y)$. For simplicity, let us focus on $k\ge 1$ and a constant $ε> 0$; then, our algorithm takes $\tilde{O}(n/a + ak^3)$ time. Unless $a=\tilde{O}(1)$ and for small enough $k$, this running time is sublinear in $n$. We also consider a very natural version that asks to find a $(k_I, k_S)$-alignment -- an alignment with at most $k_I$ indels and $k_S$ substitutions. In this setting, we give an exact algorithm and, more importantly, an $\tilde{O}(nk_I/k_S + k_S\cdot k_I^3)$-time $(1,1+ε)$-bicriteria approximation algorithm. The latter solution is based on the techniques we develop for $ED_a$ for $a=Θ(k_S / k_I)$. These bounds are in stark contrast to unit-cost edit distance, where state-of-the-art algorithms are far from achieving $(1+ε)$-approximation in sublinear time, even for a favorable choice of $k$.

International audience

The suffix array, describing the lexicographical order of suffixes of a given text, and the suffix tree, a path-compressed trie of all suffixes, are the two most fundamental data structures for string processing, with plethora of applications in data compression, bioinformatics, and information retrieval. For a length-n text, however, they use Θ(n log n) bits of space, which is often too costly. To address this, Grossi and Vitter [STOC 2000] and, independently, Ferragina and Manzini [FOCS 2000] introduced space-efficient versions of the suffix array, known as the compressed suffix array (CSA) and the FM-index. Sadakane [SODA 2002] then showed how to augment them to obtain the compressed suffix tree (CST). For a length-n text over an alphabet of size σ, these structures use only

Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O(n+k2) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.

While the$k$th order empirical entropy is an accepted measure of the compressibility of individual sequences on classical text collections, it is useful only for small values of$k$and thus fails to capture the compressibility of repetitive sequences. In the absence of an established way of quantifying the latter, ad-hoc measures like the size$z$of the Lempel–Ziv parse are frequently used to estimate repetitiveness. The size$b \le z$of the smallest bidirectional macro scheme captures better what can be achieved via copy-paste processes, though it is NP-complete to compute, and it is not monotone upon appending symbols. Recently, a more principled measure, the size$\gamma $of the smalleststring attractor, was introduced. The measure$\gamma \le b$lower-bounds all the previous relevant ones, while length-$n$strings can be represented and efficiently indexed within space$O\left({\gamma \log \frac {n}{\gamma }}\right)$, which also upper-bounds many measures, including$z$. Although$\gamma $is arguably a better measure of repetitiveness than$b$, it is also NP-complete to compute and not monotone, and it is unknown if one can represent all strings in$o(\gamma \log n)$space. In this paper, we study an even smaller measure,$\delta \le \gamma $, which can be computed in linear time, is monotone, and allows encoding every string in$O\left({\delta \log \frac {n}{\delta }}\right)$space because$z = O\left({\delta \log \frac {n}{\delta }}\right)$. We argue that$\delta $better captures the compressibility of repetitive strings. Concretely, we show that (1)$\delta $can be strictly smaller than$\gamma $, by up to a logarithmic factor; (2) there are string families needing$\Omega \left({\delta \log \frac {n}{\delta }}\right)$space to be encoded, so this space is optimal for every$n$and$\delta $; (3) one can build run-length context-free grammars of size$O\left({\delta \log \frac {n}{\delta }}\right)$, whereas the smallest (non-run-length) grammar can be up to$\Theta (\log n/\log \log n)$times larger; and (4) within$O\left({\delta \log \frac {n}{\delta }}\right)$space, we can not only represent a string but also offer logarithmic-time access to its symbols, computation of substring fingerprints, and efficient indexed searches for pattern occurrences. We further refine the above results to account for the alphabet size$\sigma $of the string, showing that$\Theta \left({\delta \log \frac {n\log \sigma }{\delta \log n}}\right)$space is necessary and sufficient to represent the string and to efficiently support access, fingerprinting, and pattern matching queries.

The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length $m$ and all length-$m$ substrings of a given text of length $n\ge m$. We focus on the $k$-mismatch version of the problem, where a distance needs to be returned only if it does not exceed a threshold $k$. We assume $n\le 2m$ (in general, one can partition the text into overlapping blocks). In this work, we show data structures for the dynamic version of this problem supporting two operations: An update performs a single-letter substitution in the pattern or the text, and a query, given an index $i$, returns the Hamming distance between the pattern and the text substring starting at position $i$, or reports that it exceeds $k$. First, we show a data structure with $\tilde{O}(1)$ update and $\tilde{O}(k)$ query time. Then we show that $\tilde{O}(k)$ update and $\tilde{O}(1)$ query time is also possible. These two provide an optimal trade-off for the dynamic $k$-mismatch problem with $k \le \sqrt{n}$: we prove that, conditioned on the strong 3SUM conjecture, one cannot simultaneously achieve $k^{1-Ω(1)}$ time for all operations. For $k\ge \sqrt{n}$, we give another lower bound, conditioned on the Online Matrix-Vector conjecture, that excludes algorithms taking $n^{1/2-Ω(1)}$ time per operation. This is tight for constant-sized alphabets: Clifford et al. (STACS 2018) achieved $\tilde{O}(\sqrt{n})$ time per operation in that case, but with $\tilde{O}(n^{3/4})$ time per operation for large alphabets. We improve and extend this result with an algorithm that, given $1\le x\le k$, achieves update time $\tilde{O}(\frac{n}{k} +\sqrt{\frac{nk}{x}})$ and query time $\tilde{O}(x)$. In particular, for $k\ge \sqrt{n}$, an appropriate choice of $x$ yields $\tilde{O}(\sqrt[3]{nk})$ time per operation, which is $\tilde{O}(n^{2/3})$ when no threshold $k$ is provided.

We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a threshold $k>0$, and we are to report all starting positions of fragments of $T$ (called occurrences) that are at distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such occurrence exists. All previous results for approximate CPM were either average-case upper bounds or heuristics, except for the work of Charalampopoulos et al. [CKP$^+$, JCSS'21], who considered only the Hamming distance. For the reporting version of the approximate CPM problem, under the Hamming distance we improve upon the main algorithm of [CKP$^+$, JCSS'21] from ${\cal O}(n+(n/m)\cdot k^4)$ to ${\cal O}(n+(n/m)\cdot k^3)$ time; for the edit distance, we give an ${\cal O}(nk^2)$-time algorithm. We also consider the decision version of the approximate CPM problem. Under the Hamming distance, we obtain an ${\cal O}(n+(n/m)\cdot k^2\log k/\log\log k)$-time algorithm, which nearly matches the algorithm by Chan et al. [CGKKP, STOC'20] for the standard counterpart of the problem. Under the edit distance, the ${\cal O}(nk\log^2 k)$ running time of our algorithm nearly matches the ${\cal O}(nk)$ running time of the Landau-Vishkin algorithm [LV, J. Algorithms'89]. As a stepping stone, we propose an ${\cal O}(nk\log^2 k)$-time algorithm for the Longest Prefix $k'$-Approximate Match problem, proposed by Landau et al. [LMS, SICOMP'98], for all $k'\in \{1,\dots,k\}$. We give a conditional lower bound that suggests a polynomial separation between approximate CPM under the Hamming distance over the binary alphabet and its non-circular counterpart. We also show that a strongly subquadratic-time algorithm for the decision version of approximate CPM under edit distance would refute SETH.

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG’10); however, Mao (FOCS’21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication.Given a parameter k as an upper bound on the distance, an $\mathcal{O}(n+k^{2})$-time algorithm for edit distance has been known since the 1980s due to works of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88). The existence of an $\tilde{\mathcal{O}}(n+poly(k))$-time algorithm for tree edit distance has been posed as open question, e.g., by Akmal and Jin (ICALP’21), who give a stateof-the-art $O(nk^{2})$-time algorithm. In this paper, we answer this question positively.

We consider the approximate pattern matching problem under the edit distance. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to find the starting positions of all substrings of T that can be transformed to P with at most k edits. More than 20 years ago, Cole and Hariharan [SODA’98, J. Comput.’02] gave an $\mathcal{O}(n+k^{4}\cdot n/m)$ time algorithm for this classic problem, and this runtime has not been improved since.Here, we present an algorithm that runs in time $\mathcal{O}\left(n+ k^{3.5}\sqrt{\log m\log k}\cdot n/m\right)$, thus breaking through this longstanding barrier. In the case where $n^{1/4+\varepsilon}\leq k\leq n^{2/5-\varepsilon}$ for some arbitrarily small positive constant $\varepsilon$, our algorithm improves over the state-of-the-art by polynomial factors: it is polynomially faster than both the algorithm of Cole and Hariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau and Vishkin [STOC’86, J. Algorithms’89].We observe that the bottleneck case of the alternative $\mathcal{O}(n+k^4 \cdot n / m$-time algorithm of Charalampopoulos, Kociumaka, and Wellnitz [FOCS’20] is when the text and the pattern are (almost) periodic. Our new algorithm reduces this case to a new Dynamic Puzzle Matching problem, which we solve by building on tools developed by Tiskin [SODA’10, Algorithmica’15] for the so-called seaweed monoid of permutation matrices. Our algorithm relies only on a small set of primitive operations on strings and thus also applies to the fully-compressed setting (where text and pattern are given as straight-line programs) and to the dynamic setting (where we maintain a collection of strings under creation, splitting, and concatenation), improving over the state of the art.

We study the problem of approximating edit distance in sublinear time. This is formalized as the $(k,\ k^{\mathrm{c}})$-GAP EDIT DISTANCE problem, where the input is a pair of strings $X, \mathrm{Y}$ and parameters $k, c\gt 1$, and the goal is to return YES if ED(X, Y) $\leq k$, NO if ED(X, Y) $\gt k^{\mathrm{c}}$, and an arbitrary answer when $k\lt $ ED(X, Y) $\leq k^{\mathrm{c}}$. Recent years have witnessed significant interest in designing sublinear-time algorithms for GAP EDIT DISTANCE.In this work, we resolve the non-adaptive query complexity of GAP EDIT DISTANCE for the entire range of parameters, improving over a sequence of previous results. Specifically, we design a non-adaptive algorithm with query complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}.5})$, and we further prove that this bound is optimal up to polylogarithmic factors.Our algorithm also achieves optimal time complexity $\tilde{O}(n/k^{\mathrm{c}-\mathrm{O}.5})$ whenever $ c\geq$ 1.5. For $1 \lt c\lt $ 1.5, the running time of our algorithm is $\tilde{O}(n/k^{2\mathrm{c}-2})$. In the restricted case of $k^{\mathrm{c}}=\Omega(n)$, this matches a known result [Batu, Ergün, Kilian, Magen, Raskhodnikova, Rubinfeld, and Sami; STOC 2003], and in all other (nontrivial) cases, our running time is strictly better than all previous algorithms, including the adaptive ones. However, independent work of Bringmann, Cassis, Fischer, and Nakos [STOC 2022] provides an adaptive algorithm that bypasses the non-adaptive lower bound, but only for small enough k and c.

The Dyck language, which consists of well-balanced sequences of parentheses, is one of the most fundamental context-free languages. The Dyck edit distance quantifies the number of edits (character insertions, deletions, and substitutions) required to make a given length-n parenthesis sequence well-balanced. RNA Folding involves a similar problem, where a closing parenthesis can match an opening parenthesis of the same type irrespective of their ordering. For example, in RNA Folding, both () and )( are valid matches, whereas the Dyck language only allows () as a match. Both of these problems have been studied extensively in the literature. Using fast matrix multiplication, it is possible to compute their exact solutions in time O(n^2.687) (Chi, Duan, Xie, Zhang, STOC'22), and a (1+ε)-multiplicative approximation is known with a running time of Ω(n^2.372). The impracticality of fast matrix multiplication often makes combinatorial algorithms much more desirable. Unfortunately, it is known that the problems of (exactly) computing the Dyck edit distance and the folding distance are at least as hard as Boolean matrix multiplication. Thereby, they are unlikely to admit truly subcubic-time combinatorial algorithms. In terms of fast approximation algorithms that are combinatorial in nature, the state of the art for Dyck edit distance is an O(log n)-factor approximation algorithm that runs in near-linear time (Saha, FOCS'14), whereas for RNA Folding only an ε n-additive approximation in Õ(n²/ε) time (Saha, FOCS'17) is known. In this paper, we make substantial improvements to the state of the art for Dyck edit distance (with any number of parenthesis types). We design a constant-factor approximation algorithm that runs in Õ(n^1.971) time (the first constant-factor approximation in subquadratic time). Moreover, we develop a (1+ε)-factor approximation algorithm running in Õ(n²/ε) time, which improves upon the earlier additive approximation. Finally, we design a (3+ε)-approximation that takes Õ(nd/ε) time, where d ≥ 1 is an upper bound on the sought distance. As for RNA folding, for any s ≥ 1, we design a factor-s approximation algorithm that runs in O(n+(n/s)³) time. To the best of our knowledge, this is the first nontrivial approximation algorithm for RNA Folding that can go below the n² barrier. All our algorithms are combinatorial in nature.

A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform S into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses S and a positive integer k, and the goal is to compute the Dyck edit distance of S only if the distance is at most k, and otherwise report that the distance is larger than k. Backurs and Onak [PODS'16] showed that the threshold Dyck edit distance problem can be solved in O(n + k16) time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs O(n + k4.782036) time with high probability or O(n + k4.853059) deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant's parsing algorithm.

Real-world data often comes in compressed form. Analyzing compressed data directly (without first decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and try to quantify the gain in time complexity when the underlying data is highly compressible. We consider grammar compression, which unifies many practically relevant compression schemes such as the Lempel–Ziv family, dictionary methods, and others. For two strings of total length N and total compressed size n, it is known that the edit distance and a longest common subsequence (LCS) can be computed exactly in time Õ(nN), as opposed to O(N2) for the uncompressed setting. Many real-world applications need to align multiple sequences simultaneously, and the fastest known exact algorithms for median edit distance and LCS of k strings run in O(Nk) time, whereas the one for center edit distance has a time complexity of O(N2k). This naturally raises the question if compression can help to reduce the running time significantly for k ≥ 3, perhaps to O(Nk/2 nk/2) or, more optimistically, to O(Nnk–1).1 Unfortunately, we show new lower bounds that rule out any improvement beyond Ω(Nk–1 n) time for any of these problems assuming the Strong Exponential Time Hypothesis (SETH), where again N and n represent the total length and the total compressed size, respectively. This answers an open question of Abboud, Backurs, Bringmann, and Künnemann (FOCS'17). In presence of such negative results, we ask if allowing approximation can help, and we show that approximation and compression together can be surprisingly effective for both multiple and two strings. We develop an Õ(Nk/2 nk/2)-time FPTAS for the median edit distance of k sequences, leading to a saving of nearly half the dimensions for highly-compressible sequences. In comparison, no O(Nk–Ω(1))-time PTAS is known for the median edit distance problem in the uncompressed setting. We obtain an improvement from for the center edit distance problem. For two strings, we get an -time FPTAS for both edit distance and LCS; note that this running time is o(N) whenever n ≪ N1/4. In contrast, for uncompressed strings, there is not even a subquadratic algorithm for LCS that has less than polynomial gap in the approximation factor. Building on the insight from our approximation algorithms, we also obtain several new and improved results for many fundamental distance measures including the edit, Hamming, and shift distances.

The suffix array SA[1..n] of a text T of length n is a permutation of {1, …, n} describing the lexicographical ordering of suffixes of T and is considered to be one of the most important data structures for string processing, with dozens of applications in data compression, bioinformatics, and information retrieval. One of the biggest drawbacks of the suffix array is that it is very difficult to maintain under text updates: even a single character substitution can completely change the contents of the suffix array. Thus, the suffix array of a dynamic text is modelled using suffix array queries, which return the value SA[i] given any i ∈ [1..n].

Abstract Sequence mappability is an important task in genome resequencing. In the (k, m)-mappability problem, for a given sequence T of length n, the goal is to compute a table whose ith entry is the number of indices $$j \ne i$$ j ≠ i such that the length-m substrings of T starting at positions i and j have at most k mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of $$k=1$$ k = 1 . We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for $$k=O(1)$$ k = O ( 1 ) , works in $$O(n)$$ O ( n ) space and, with high probability, in $$O(n \cdot \min \{m^k,\log ^k n\})$$ O ( n · min { m k , log k n } ) time. Our algorithm requires a careful adaptation of the k-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop $$O(n^2)$$ O ( n 2 ) -time algorithms to compute all (k, m)-mappability tables for a fixed m and all $$k\in \{0,\ldots ,m\}$$ k ∈ { 0 , … , m } or a fixed k and all $$m\in \{k,\ldots ,n\}$$ m ∈ { k , … , n } . Finally, we show that, for $$k,m = \Theta (\log n)$$ k , m = Θ ( log n ) , the (k, m)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018.

In the classic longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, over an alphabet of size $σ$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. Weiner, in his seminal paper that introduced the suffix tree, presented an $O(n \log σ)$-time algorithm for this problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an $O(n)$-time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in $O(n \log σ/\log n )$ space and read in $O(n \log σ/\log n )$ time. We show that, in this model, we can compute an LCS in time $O(n \log σ/ \sqrt{\log n})$, which is sublinear in $n$ if $σ=2^{o(\sqrt{\log n})}$ (in particular, if $σ=O(1)$), using optimal space $O(n \log σ/\log n)$. In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. We then lift our ideas to the problem of computing a $k$-mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of $S$ that occurs in $T$ with at most $k$ mismatches. Thankachan et al.~showed how to compute a $k$-mismatch LCS in $O(n \log^k n)$ time for $k=O(1)$ [J. Comput. Biol. 2016]. We show an $O(n \log^{k-1/2} n)$-time algorithm, for any constant $k>0$ and irrespective of the alphabet size, using $O(n)$ space as the previous approaches. We thus notably break through the well-known $n \log^k n$ barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. [STOC 2004] for string indexing with $k$ errors.

In this work, we revisit the fundamental and well-studied problem of approximate pattern matching under edit distance. Given an integer$k$, a pattern$P$of length$m$, and a text$T$of length$n\geq m$, the task is to find substrings of$T$that are within edit distance$k$from$P$. Our main result is a streaming algorithm that solves the problem in$\tilde{\mathcal{O}}(k^{5})$space11Hereafter,$\tilde{\mathcal{O}}(\cdot)$hides a$\text{poly} (\log n)$factor. and$\tilde{\mathcal{O}}(k^{8})$amortized time per character of the text, providing answers correct with high probability. This answers a decade-old question: since the discovery of a poly ($k\ \text{log}\ n$) -space streaming algorithm for pattern matching under Hamming distance by Porat and Porat [FOCS 2009], the existence of an analogous result for edit distance remained open. Up to this work, no poly ($k\ \text{log}\ n$)-space algorithm was known even in the simpler semi-streaming model, where$T$comes as a stream but$P$is available for read-only access. In this model, we give a deterministic algorithm that achieves slightly better complexity. Our central technical contribution is a new space-efficient deterministic encoding of two strings, called the greedy encoding, which encodes a set of all alignments of cost at most$k$with a certain property (we call such alignments greedy). On strings of length at most$n$, the encoding occupies$\tilde{\mathcal{O}}(k^{2})$space. We use the encoding to compress substrings of the text that are close to the pattern. In order to do so, we compute the encoding for substrings of the text and of the pattern, which requires read-only access to the latter. In order to develop the fully streaming algorithm, we further introduce a new edit distance sketch parameterized by integers$n > k$. For any string of length at most$n$, the sketch is of size$\tilde{\mathcal{O}}\overline{(k}^{2})$, and it can be computed with an$\tilde{\mathcal{O}}(k^{2})$-space streaming algorithm. Given the sketches of two strings, in$\tilde{\mathcal{O}}(k^{3})$time we can compute their edit distance or certify that it is larger than$k$. This result improves upon$\tilde{\mathcal{O}}(k^{8})$-size sketches of Belazzougui and Zhang [FOCS 2016] and very recent$\tilde{\mathcal{O}}(k^{3})$-size sketches of Jin, Nelson, and Wu [STACS 2021].

We study dynamic algorithms for the longest increasing subsequence (LIS) problem. A dynamic LIS algorithm maintains a sequence subject to operations of the following form arriving one by one: insert an element, delete an element, or substitute an element for another. After each update, the algorithm must report the length of the longest increasing subsequence of the current sequence.

We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $$\mathsf {D}$$ in fragments of a given string T of length n. The dictionary is internal in the sense that each pattern in $$\mathsf {D}$$ is given as a fragment of T. This way, $$\mathsf {D}$$ takes space proportional to the number of patterns $$d=|\mathsf {D}|$$ rather than their total length, which could be $$\varTheta (n\cdot d)$$ . In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $$\mathsf {D}$$ in a fragment $$T[i \mathinner {.\,.}j]$$ and reporting distinct patterns from $$\mathsf {D}$$ that occur in $$T[i \mathinner {.\,.}j]$$ . We show how to construct, in $$O((n+d) \log ^{O(1)} n)$$ time, a data structure that answers each of these queries in time $$O(\log ^{O(1)} n+| output |)$$ . The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight—up to subpolynomial factors—upper and lower bounds for the case of a dynamic dictionary.

We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To achieve this result, we combine several recent findings, including string attractors —new combinatorial objects encompassing most known compressibility measures for highly repetitive texts—and grammars based on locally consistent parsing . More in detail, letγ be the size of the smallest attractor for a text T of length n . The measureγ is an (asymptotic) lower bound to the size of dictionary compressors based on Lempel–Ziv, context-free grammars, and many others. The smallest known text representations in terms of attractors use space O (γ log ( n /γ)), and our lightest indexes work within the same asymptotic space. Let ε > 0 be a suitably small constant fixed at construction time, m be the pattern length, and occ be the number of its text occurrences. Our index counts pattern occurrences in O ( m +log 2+ε n ) time and locates them in O ( m +( occ +1)log ε n ) time. These times already outperform those of most dictionary-compressed indexes, while obtaining the least asymptotic space for any index searching within O (( m + occ ),polylog, n ) time. Further, by increasing the space to O (γ log ( n /γ)log ε n ), we reduce the locating time to the optimal O ( m + occ ), and within O (γ log ( n /γ)log n ) space we can also count in optimal O ( m ) time. No dictionary-compressed index had obtained this time before. All our indexes can be constructed in O ( n ) space and O ( n log n ) expected time. As a by-product of independent interest, we show how to build, in O ( n ) expected time and without knowing the sizeγ of the smallest attractor (which is NP-hard to find), a run-length context-free grammar of size O (γ log ( n /γ)) generating (only) T . As a result, our indexes can be built without knowingγ.

The shift distance $\mathsf{sh}(S_1,S_2)$ between two strings $S_1$ and $S_2$ of the same length is defined as the minimum Hamming distance between $S_1$ and any rotation (cyclic shift) of $S_2$. We study the problem of sketching the shift distance, which is the following communication complexity problem: Strings $S_1$ and $S_2$ of length $n$ are given to two identical players (encoders), who independently compute sketches (summaries) $\mathtt{sk}(S_1)$ and $\mathtt{sk}(S_2)$, respectively, so that upon receiving the two sketches, a third player (decoder) is able to compute (or approximate) $\mathsf{sh}(S_1,S_2)$ with high probability. This paper primarily focuses on the more general $k$-mismatch version of the problem, where the decoder is allowed to declare a failure if $\mathsf{sh}(S_1,S_2)>k$, where $k$ is a parameter known to all parties. Andoni et al. (STOC'13) introduced exact circular $k$-mismatch sketches of size $\widetilde{O}(k+D(n))$, where $D(n)$ is the number of divisors of $n$. Andoni et al. also showed that their sketch size is optimal in the class of linear homomorphic sketches. We circumvent this lower bound by designing a (non-linear) exact circular $k$-mismatch sketch of size $\widetilde{O}(k)$; this size matches communication-complexity lower bounds. We also design $(1\pm \varepsilon)$-approximate circular $k$-mismatch sketch of size $\widetilde{O}(\min(\varepsilon^{-2}\sqrt{k}, \varepsilon^{-1.5}\sqrt{n}))$, which improves upon an $\widetilde{O}(\varepsilon^{-2}\sqrt{n})$-size sketch of Crouch and McGregor (APPROX'11).

We consider the problem of preprocessing a text T of length n and a dictionary 𝒟 in order to be able to efficiently answer queries CountDistinct(i,j), that is, given i and j return the number of patterns from 𝒟 that occur in the fragment T[i..j]. The dictionary is internal in the sense that each pattern in 𝒟 is given as a fragment of T. This way, the dictionary takes space proportional to the number of patterns d=|𝒟| rather than their total length, which could be Θ(n⋅ d). An 𝒪̃(n+d)-size data structure that answers CountDistinct(i,j) queries 𝒪(log n)-approximately in 𝒪̃(1) time was recently proposed in a work that introduced internal dictionary matching [ISAAC 2019]. Here we present an 𝒪̃(n+d)-size data structure that answers CountDistinct(i,j) queries 2-approximately in 𝒪̃(1) time. Using range queries, for any m, we give an 𝒪̃(min(nd/m,n²/m²)+d)-size data structure that answers CountDistinct(i,j) queries exactly in 𝒪̃(m) time. We also consider the special case when the dictionary consists of all square factors of the string. We design an 𝒪(n log² n)-size data structure that allows us to count distinct squares in a text fragment T[i..j] in 𝒪(log n) time.

We consider the problem of dynamically maintaining an optimal alignment of two strings, each of length at most n, as they undergo insertions, deletions, and substitutions of letters. The string alignment problem generalizes the longest common subsequence (LCS) problem and the edit distance problem (also with non-unit costs, as long as insertions and deletions cost the same). The conditional lower bound of Backurs and Indyk [J. Comput. 2018] for computing the LCS in the static case implies that strongly sublinear update time for the dynamic string alignment problem would refute the Strong Exponential Time Hypothesis. We essentially match this lower bound when the alignment weights are constants, by showing how to process each update in 𝒪̃(n) time. When the weights are integers bounded in absolute value by some w=n^{𝒪(1)}, we can maintain the alignment in 𝒪̃(n ⋅ min {√ n,w}) time per update. For the 𝒪̃(nw)-time algorithm, we heavily rely on Tiskin’s work on semi-local LCS, and in particular, in an implicit way, on his algorithm for computing the (min,+)-product of two simple unit-Monge matrices [Algorithmica 2015]. As for the 𝒪̃(n√n)-time algorithm, we employ efficient data structures for computing distances in planar graphs.

We revisit the k-mismatch problem in the streaming model on a pattern of length m and a streaming text of length n, both over a size-σ alphabet. The current state-of-the-art algorithm for the streaming k-mismatch problem, by Clifford et al. [SODA 2019], uses Õ(k) space and Õ(√k) worst-case time per character. The space complexity is known to be (unconditionally) optimal, and the worst-case time per character matches a conditional lower bound. However, there is a gap between the total time cost of the algorithm, which is Õ(n√k), and the fastest known offline algorithm, which costs Õ(n + min(nk/√m, σn)) time. Moreover, it is not known whether improvements over the Õ(n√k) total time are possible when using more than O(k) space. We address these gaps by designing a randomized streaming algorithm for the k-mismatch problem that, given an integer parameter k≤s≤m, uses Õ(s) space and costs Õ(n+min(nk²/m, nk/√s, σnm/s)) total time. For s=m, the total runtime becomes Õ(n + min(nk/√m, σn)), which matches the time cost of the fastest offline algorithm. Moreover, the worst-case time cost per character is still Õ(√k).

In the problem of the longest common substring with k mismatches we are given two strings X, Y and must find the maximal length 𝓁 such that there is a length-𝓁 substring of X and a length-𝓁 substring of Y that differ in at most k positions. The length 𝓁 can be used as a robust measure of similarity between X, Y. In this work, we develop new approximation algorithms for computing 𝓁 that are significantly more efficient that previously known solutions from the theoretical point of view. Our approach is simple and practical, which we confirm via an experimental evaluation, and is probably close to optimal as we demonstrate via a conditional lower bound.

We consider the problem of finding, given two documents of total length n, a longest string occurring as a substring of both documents. This problem, known as the Longest Common Substring (LCS) problem, has a classic 𝒪(n)-time solution dating back to the discovery of suffix trees (Weiner, 1973) and their efficient construction for integer alphabets (Farach-Colton, 1997). However, these solutions require Θ(n) space, which is prohibitive in many applications. To address this issue, Starikovskaya and Vildhøj (CPM 2013) showed that for n^{2/3} ≤ s ≤ n, the LCS problem can be solved in 𝒪(s) space and 𝒪̃(n²/s) time. Kociumaka et al. (ESA 2014) generalized this tradeoff to 1 ≤ s ≤ n, thus providing a smooth time-space tradeoff from constant to linear space. In this paper, we obtain a significant speed-up for instances where the length L of the sought LCS is large. For 1 ≤ s ≤ n, we show that the LCS problem can be solved in 𝒪(s) space and 𝒪̃(n²/(L⋅s) +n) time. The result is based on techniques originating from the LCS with Mismatches problem (Flouri et al., 2015; Charalampopoulos et al., CPM 2018), on space-efficient locally consistent parsing (Birenzwige et al., SODA 2020), and on the structure of maximal repetitions (runs) in the input documents.

For a text T[1,n], a Longest Common Extension (LCE) query lce_T(i,j) asks for the length of the longest common prefix of the suffixes T[i,n] and T[j,n] identified by their starting positions 1 ≤ i,j ≤ n. A classic problem in stringology asks to preprocess a static text T[1,n] over an alphabet of size σ so that LCE queries can be efficiently answered on-line. Since its introduction in the 1980’s, this problem has found numerous applications: in suffix sorting, edit distance computation, approximate pattern matching, regularities finding, string mining, and many more. Text-book solutions offer O(n) preprocessing time and O(1) query time, but they employ memory-heavy data structures, such as suffix arrays, in practice several times bigger than the text itself. Very recently, more space efficient solutions using O(nlogσ) bits of total space or even only O(log n) bits of extra space have been proposed: string synchronizing sets [Kempa and Kociumaka, STOC'19, and Birenzwige et al., SODA'20] and in-place fingerprinting [Prezza, SODA'18]. The goal of this article is to present well-engineered implementations of these new solutions and study their practicality on a commonly agreed text corpus. We show that both perform extremely well in practice, with space consumption of only around 10% of the input size for string synchronizing sets (around 20% for highly repetitive texts), and essentially no extra space for fingerprinting. Interestingly, our experiments also show that both solutions become much faster than naive scanning even for finding common prefixes of moderate length, contradicting a common belief that sophisticated data structures for LCE queries are not competitive with naive approaches [Ilie and Tinta, SPIRE'09].

In the approximate pattern matching problem, given a text T, a pattern P, and a threshold k, the task is to find (the starting positions of) all substrings of T that are at distance at most k from P. We consider the two most fundamental string metrics: Under the Hamming distance, we search for substrings of T that have at most k mismatches with P, while under the edit distance, we search for substrings of T that can be transformed to P with at most k edits. Exact occurrences of P in T have a very simple structure: If we assume for simplicity that |P|2) k-mismatch occurrences of P in T, or both P and T are at Hamming distance O(k) from strings with a common string period of length O(m/k). We tighten this characterization by showing that there are O(k) k-mismatch occurrences in the non-periodic case, and we lift it to the edit distance setting, where we tightly bound the number of k-edit occurrences by O(k2) in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. In particular, we provide meta-algorithms that only rely on a small set of primitive operations. We showcase the generality of our meta-algorithms with results for the fully compressed setting, the dynamic setting, and the standard setting.

The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main component of popular lossless compression programs (such as bzip2) as well as recent powerful compressed indexes (such as r-index [Gagie et al., J. ACM, 2020]), central in modern bioinformatics. The compression ratio of BWT is quantified by the number r of equal-letter runs. Despite the practical significance of BWT, no non-trivial bound on the value of r is known. This is in contrast to nearly all other known compression methods, whose sizes have been shown to be either always within a polylogn factor (where n is the length of text) from z, the size of Lempel-Ziv (LZ77) parsing of the text, or significantly larger in the worst case (by a nεfactor for ). In this paper, we show that r=O(zlog2n) holds for every text. This result has numerous implications for text indexing and data compression; for example: (1) it proves that many results related to BWT automatically apply to methods based on LZ77, e.g., it is possible to obtain functionality of the suffix tree in O(zpolylog n) space; (2) it shows that many text processing tasks can be solved in the optimal time assuming the text is compressible using LZ77 by a sufficiently large polylogn factor; (3) it implies the first non-trivial relation between the number of runs in the BWT of the text and its reverse. In addition, we provide an O(z polylog n)-time algorithm converting the LZ77 parsing into the run-length compressed BWT. To achieve this, we develop a number of new data structures and techniques of independent interest. In particular, we introduce a notion of compressed string synchronizing sets (generalizing the recently introduced powerful technique of string synchronizing sets [STOC 2019]) and show how to efficiently construct them. Next, we propose a new variant of wavelet trees for sequences of long strings, establish a nontrivial bound on their size, and describe efficient construction algorithms. Finally, we describe new indexes that can be constructed directly from the LZ77-compressed text and efficiently support pattern matching queries on substrings of the text.

In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give a greedy algorithm that distinguishes in time ~O([n/k]+k2) between length-n input strings with edit distance at most k and those with edit distance more than 4k2. This is an improvement and a simplification upon the main result of [Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs Θ(k2) gap edit distance problem is solved in ~O([n/k]+k3) time. We further generalize our result to solve the k vs αk gap edit distance problem in time ~O([n/(α)]+k2+[k/(α)]√{nk}), strictly improving upon the previously known bound ~O([n/(α)]+k3). Finally, we show that if the input strings do not have long highly periodic substrings, then the gap edit distance problem can be solved in sublinear time within any factor . Specifically, if the strings contain no substring of length l with the shortest period of length at most 2k, then the k vs (1+ε)k gap edit distance problem can be solved in time ~O([n/(ε2k)]+k2l). We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our ~O([n/p])-time procedure yields an embedding with distortion k2p, where k is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between [(k-p+1)/p] and k2with good probability. This generalizes the linear-time embedding of [Chakraborty, Goldenberg, Koucký, STOC 2016], where the resultant Hamming distance is between k and k2. Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.

We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size σ, compute the Hamming distance (i.e., the number of mismatches) between the pattern and the text at every location. Several randomized (1+ε)-approximation algorithms have been proposed in the literature (e.g., by Karloff (Inf. Proc. Lett., 1993), Indyk (FOCS 1998), and Kopelowitz and Porat (SOSA 2018)), with running time of the form O(ε−O(1) nlognlogm), all using fast Fourier transform (FFT). We describe a simple randomized (1+ε)-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results (all Monte-Carlo randomized) in different settings:

In the order-preserving model, two strings match if they share the same relative order between the characters at the corresponding positions. This model is quite recent, but it has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O(n), O(nlog⁡log⁡n), O(nlog2⁡log⁡n/log⁡log⁡log⁡n), O(nlog⁡n) depending on the type of periodicity. In the most general variant, the number of different op-periods can be as big as Ω(n2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of op-periods. In particular, we characterize the Fine–Wilf property for coprime op-periods.

A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. Our first contribution is a linear-time algorithm computing a linear-size representation of all seeds of a word (the number of seeds might be quadratic). In particular, one can easily derive the shortest seed and the number of seeds from our representation. Thus, we solve an open problem stated in a survey by Smyth from 2000 and improve upon a previous O ( n log n )-time algorithm by Iliopoulos et al. from 1996. Our approach is based on combinatorial relations between seeds and subword complexity (used here for the first time in the context of seeds). In previous papers, compact representations of seeds consisted of two independent parts operating on the suffix tree of the input word and the suffix tree of its reverse, respectively. Our second contribution is a novel and significantly simpler representation of all seeds that avoids dealing with the suffix tree of the reversed word. This result is also of independent interest from a combinatorial point of view. A preliminary version of this work, with a much more complex algorithm constructing a representation of seeds on two suffix trees, was presented at the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12).

We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings $S$ and $T$ of length $n$, we are to compute the longest factor of $S$ whose cyclic shift occurs as a factor of $T$. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in $O(n \log^5 n)$ time.

The k -mismatch problem consists in computing the Hamming distance between a pattern P of length m and every length- m substring of a text T of length n , if this distance is no more than k . In many real-world applications, any cyclic shift of P is a relevant pattern, and thus one is interested in computing the minimal distance of every length- m substring of T and any cyclic shift of P . This is the circular pattern matching with k mismatches ( k -CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the k -CPM problem. Specifically, we show an \(\mathcal {O}(nk)\) -time algorithm and an \(\mathcal {O}(n+\frac{n}{m}\,{\small k^5})\) -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k -mismatch problem [Bringmann et al., SODA 2019].

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard but fixed-parameter tractable (when the locality number or the alphabet size is treated as a parameter), and can be approximated with ratio O(sqrt{log{opt}} log n). As a by-product, we also relate cutwidth via the locality number to pathwidth, which is of independent interest, since it improves the best currently known approximation algorithm for cutwidth. In addition to these main results, we also consider the possibility of greedy-based approximation algorithms for the locality number.

We show that the edit distance between two run-length encoded strings of compressed lengths $m$ and $n$ respectively, can be computed in $\mathcal{O}(mn\log(mn))$ time. This improves the previous record by a factor of $\mathcal{O}(n/\log(mn))$. The running time of our algorithm is within subpolynomial factors of being optimal, subject to the standard SETH-hardness assumption. This effectively closes a line of algorithmic research first started in 1993.

We consider the streaming complexity of a fundamental task in approximate pattern matching: the k-mismatch problem. In this problem, we must compute Hamming distances between a pattern of length n and all length-n substrings of a text for which the Hamming distance does not exceed a given threshold k. In our problem formulation, we report not only the Hamming distance but also, on demand, the full mismatch information, that is the list of mismatched pairs of symbols and their indices. The twin challenges of streaming pattern matching derive from the need both to achieve small working space and also to guarantee that every arriving input symbol is processed quickly. We present a streaming algorithm for the k-mismatch problem which uses bits of space and spends time on each symbol of the input stream. In our formulation, the pattern is also in the stream, arriving directly before the text. The running time almost matches the classic offline solution [5] and the space usage is within a logarithmic factor of optimal. Our new algorithm therefore effectively resolves and also extends a problem first introduced in FOCS’09 [38]. En route to this solution, we also give a deterministic -bit encoding of all the alignments with Hamming distance at most k of a length-n pattern within a text of length O(n). This secondary result provides an optimal solution to a natural encoding problem which may be of independent interest.

Burrows–Wheeler transform (BWT) is an invertible text transformation that, given a text T of length n, permutes its symbols according to the lexicographic order of suffixes of T. BWT is one of the most heavily studied algorithms in data compression with numerous applications in indexing, sequence analysis, and bioinformatics. Its construction is a bottleneck in many scenarios, and settling the complexity of this task is one of the most important unsolved problems in sequence analysis that has remained open for 25 years. Given a binary string of length n, occupying O(n/logn) machine words, the BWT construction algorithm due to Hon et al. (SIAM J. Comput., 2009) runs in O(n) time and O(n/logn) space. Recent advancements (Belazzougui, STOC 2014, and Munro et al., SODA 2017) focus on removing the alphabet-size dependency in the time complexity, but they still require Ω(n) time. Despite the clearly suboptimal running time, the existing techniques appear to have reached their limits.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most $$\sqrt{17}+4\approx 8.123$$ times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time $$2^{C_g \cdot k^2 \log k} n^{\mathcal {O}(1)}$$ , where k is the size of the deletion set, $$C_g$$ is a constant depending on the Euler genus g of the target surface, and n is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time $$2^{\mathcal {O}((t+g) \log (t+g))} n$$ given a tree decomposition of the input graph of width t. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter (Algorithmica 62(3–4):807–822, 2012. https://doi.org/10.1007/s00453-010-9484-z ), Kawarabayashi (in: 50th annual IEEE symposium on foundations of computer science, FOCS 2009, IEEE Computer Society, pp 639–648, 2009. https://doi.org/10.1109/FOCS.2009.45 ) and Jansen et al. (in: Chekuri (ed) 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, SIAM, pp 1802–1811, 2014. https://doi.org/10.1137/1.9781611973402.130 ).

Abstract In the longest common substring problem, we are given two strings of length n and must find a substring of maximal length that occurs in both strings. It is well known that the problem can be solved in linear time, but the solution is not robust and can vary greatly when the input strings are changed even by one character. To circumvent this, Leimeister and Morgenstern introduced the problem of the longest common substring with k mismatches. Lately, this problem has received a lot of attention in the literature. In this paper, we first show a conditional lower bound based on the SETH hypothesis implying that there is little hope to improve existing solutions. We then introduce a new but closely related problem of the longest common substring with approximately k mismatches and use locality-sensitive hashing to show that it admits a solution with strongly subquadratic running time. We also apply these results to obtain a strongly subquadratic-time 2-approximation algorithm for the longest common substring with k mismatches problem and show conditional hardness of improving its approximation ratio.

We study pattern matching problems on two major representations of uncertain sequences used in molecular biology: weighted sequences (also known as position weight matrices, PWM) and profiles (scoring matrices). In the simple version, in which only the pattern or only the text is uncertain, we obtain efficient algorithms with theoretically-provable running times using a variation of the lookahead scoring technique. We also consider a general variant of the pattern matching problems in which both the pattern and the text are uncertain. Central to our solution is a special case where the sequences have equal length, called the consensus problem. We propose algorithms for the consensus problem parameterised by the number of strings that match one of the sequences. As our basic approach, a careful adaptation of the classic meet-in-the-middle algorithm for the knapsack problem is used. On the lower bound side, we prove that our dependence on the parameter is optimal up to lower-order terms conditioned on the optimality of the original algorithm for the knapsack problem. Therefore, we make an effort to keep the lower order terms of the complexities of our algorithms as small as possible.

In the Longest Common Factor with k Mismatches (LCF_k) problem, we are given two strings X and Y of total length n, and we are asked to find a pair of maximal-length factors, one of X and the other of Y, such that their Hamming distance is at most k. Thankachan et al. [Thankachan et al. 2016] show that this problem can be solved in O(n log^k n) time and O(n) space for constant k. We consider the LCF_k(l) problem in which we assume that the sought factors have length at least l. We use difference covers to reduce the LCF_k(l) problem with l=Omega(log^{2k+2}n) to a task involving m=O(n/log^{k+1}n) synchronized factors. The latter can be solved in O(m log^{k+1}m) time, which results in a linear-time algorithm for LCF_k(l) with l=Omega(log^{2k+2}n). In general, our solution to the LCF_k(l) problem for arbitrary l takes O(n + n log^{k+1} n/sqrt{l}) time.

We consider the problem of edit distance in which block operations are allowed, i.e. we ask for the minimal number of (block) operations that are needed to transform a string s to t. We give O(log n) approximation algorithms, where n is the total length of the input strings, for the variants of the problem which allow the following sets of operations: block move; block move and block delete; block move and block copy; block move, block copy, and block uncopy. The results still hold if we additionally allow any of the following operations: character insert, character delete, block reversal, or block involution (involution is a generalisation of the reversal). Previously, algorithms only for the first and last variant were known, and they had approximation ratios O(log n log^*n) and O(log n (log^*n)^2), respectively. The edit distance with block moves is equivalent, up to a constant factor, to the common string partition problem, in which we are given two strings s, t and the goal is to partition s into minimal number of parts such that they can be permuted in order to obtain t. Thus we also obtain an O(log n) approximation for this problem (compared to the previous O(log n log^* n)). The results use a simplification of the previously used technique of locally consistent parsing, which groups short substrings of a string into phrases so that similar substrings are guaranteed to be grouped in a similar way. Instead of a sophisticated parsing technique relying on a deterministic coin tossing, we use a simple one based on a partition of the alphabet into two subalphabets. In particular, this lowers the running time from O(n log^* n) to O(n). The new algorithms (for block copy or block delete) use a similar algorithm, but the analysis is based on a specially tuned combinatorial function on sets of numbers.

A border u of a word w is a proper factor of w occurring both as a prefix and as a suffix. The maximal unbordered factor of w is the longest factor of w which does not have a border. Here an O(n log n)-time with high probability (or O(n log n log^2 log n)-time deterministic) algorithm to compute the Longest Unbordered Factor Array of w for general alphabets is presented, where n is the length of w. This array specifies the length of the maximal unbordered factor starting at each position of w. This is a major improvement on the running time of the currently best worst-case algorithm working in O(n^{1.5}) time for integer alphabets [Gawrychowski et al., 2015].

In this paper, we study the fundamental problem of maintaining a dynamic collection of strings under the following operations: •• make_string – add a string of constant length,•• concat – concatenate two strings,•• split – split a string into two at a given position,•• compare – find the lexicographical order (less, equal, greater) between two strings,•• LCP – calculate the longest common prefix of two strings. We develop a generic framework for dynamizing the recompression method recently introduced by Jeż [J. ACM, 2016]. It allows us to present an efficient data structure for the above problem, where an update requires only O(log n) worst-case time with high probability, with n being the total length of all strings in the collection, and a query takes constant worst-case time. On the lower bound side, we prove that even if the only possible query is checking equality of two strings, either updates or queries must take amortized Ω(log n) time; hence our implementation is optimal.

We consider the Abelian longest common factor problem in two scenarios: when input strings are uncompressed and are of length at most n, and when the input strings are run-length encoded and their compressed representations have size at most m. The alphabet size is denoted by σ. For the uncompresse d problem, we show an O(n2/ log1+1/σ n)-time and 𝒪(n)-space algorithm in the case of σ = 𝒪(1), making a non-trivial use of tabulation. For the RLE-compressed problem, we show two algorithms: one working in 𝒪(m2σ2 log3m) time and 𝒪(m(σ2+log2m)) space, which employs line sweep, and one that works in 𝒪(m3) time and 𝒪(m) space that applies in a careful way a sliding-window-based approach. The latter improves upon the previously known 𝒪(nm2)-time and 𝒪(m4)-time algorithms that were recently developed by Sugimoto et al. (IWOCA 2017) and Grabowski (SPIRE 2017), respectively.

Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographical order. In some applications, such as sparse text indexing, we work with a subset of b interesting suffixes, which are stored in the so-called sparse suffix tree. Because the size of this structure is Θ(b), it is natural to seek a construction algorithm using only O(b) words of space assuming read-only random access to the text. We design a linear-time Monte Carlo algorithm for this problem, hence resolving an open question explicitly stated by Bille et al. [TALG 2016]. The best previously known algorithm by I et al. [STACS 2014] works in O(n log b) time. As opposed to previous solutions, which were based on the divide-and-conquer paradigm, our solution proceeds in n/b rounds. In the r-th round, we consider all suffixes starting at positions congruent to r modulo n/b. By maintaining rolling hashes, we can lexicographically sort all interesting suffixes starting at such positions, and then we can merge them with the already considered suffixes. For efficient merging, we also need to answer LCE queries efficiently (and in small space). By plugging in the structure of Bille et al. [CPM 2015] we obtain O(n + b log b) time complexity. We improve this structure by a recursive application of the so-called difference covers, which then implies a linear-time sparse suffix tree construction algorithm. We complement our Monte Carlo algorithm with a deterministic verification procedure. The verification takes time, which improves upon the bound of O(n log b) obtained by I et al. [STACS 2014]. This is obtained by first observing that the pruning done inside the previous solution has a rather clean description using the notion of graph spanners with small multiplicative stretch. Then, we are able to decrease the verification time by applying difference covers twice. Combined with the Monte Carlo algorithm, this gives us an and O(b)-space Las Vegas algorithm.

We introduce efficient indexes for a problem in non-standard stringology: jumbled pattern matching. An index is a data structure constructed for a text of length n over an alphabet of size $$\sigma $$ that can answer queries asking if the text contains a fragment which is jumbled (Abelian) equivalent to a pattern, specified by its so-called Parikh vector. We denote the length of the pattern by m. Moosa and Rahman (J Discrete Algorithms 10:5–9, 2012) gave an index for the case of binary alphabets with $$\mathcal {O}\left( \frac{n^2}{(\log n)^2}\right) $$ -time construction in the word-RAM model. Several earlier papers stated as an open problem the existence of an efficient solution for larger alphabets. In this paper we develop an index for any constant-sized alphabet. The construction involves a trade-off parameter, which in particular lets us achieve the following complexities: $$\mathcal {O}(n^{2-\delta })$$ space and $$\mathcal {O}(m^{(2\sigma -1)\delta })$$ query time for any $$0<\delta <1$$ , or $$\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) $$ space and polylogarithmic, $$o(\log ^{2\sigma -1} m)$$ , query time. The construction time in both cases is subquadratic: $$\mathcal {O}\left( \frac{n^2 (\log \log n)^2}{\log n}\right) $$ in the word-RAM model (using bit-parallelism). Our construction algorithms are randomized (Las Vegas, running time w.h.p.), which is due to the usage of perfect hashing. On the other hand, all queries are answered deterministically. A preliminary version of this work appeared at ESA 2013 (Kociumaka et al. in Algorithms, ESA 2013. LNCS, vol 8125. Springer, Berlin, pp. 625–636, 2013). Here we improve it in several ways. We achieve $$\mathcal {O}(n^2)$$ -time construction of the index with $$\mathcal {O}(n^{2-\delta })$$ space and $$\mathcal {O}(m^{(2\sigma -1)\delta })$$ query time, which was not present in the preliminary version. We also extend the index so that the position of the leftmost occurrence of the query pattern is provided at no additional cost in the complexity; this required rather nontrivial changes in the construction algorithm.

In this paper we consider substrings of an unrooted edge-labeled tree, which are defined as the composite labels of simple paths. We study how the number of distinct repetitive substrings depends on their exponent $$\alpha $$ . An $$\alpha $$ -power is defined as a string U with an (integral, not necessarily shortest) period $$|U|/\alpha $$ . For example, squares are 2-powers and cubes are 3-powers. We investigate the asymptotic growth of the maximal number $$\textsf {powers}_{\alpha }(n)$$ of distinct $$\alpha $$ -powers occurring as substrings of a tree with n nodes. The maximum number of such powers behaves much unlike in strings. In a previous work (CPM 2012. LNCS, vol 7354. Springer, Berlin, pp 27–40, 2012. It was proved that the number of different squares in a tree is $$\textsf {powers}_2(n) = \varTheta (n^{4/3})$$ . We extend this result and analyze powers of arbitrary rational exponent $$\alpha \ge 1$$ . We identify two phase-transition thresholds: This is a full version of a paper presented at CPM 2015. LNCS, vol 9133. Springer, Berlin, pp 284–294, 2015. Compared to the earlier version, we improve our main technical contribution, i.e., the upper bound on the number of cubes in a tree, from $$\mathcal {O}(n \log n)$$ to $$\mathcal {O}(n)$$ . This lets us obtain a tight asymptotic characterization of the $$\textsf {powers}$$ function.

The problem of finding factors of a text string which are identical or similar to a given pattern string is a central problem in computer science. A generalised version of this problem consists in implementing an index over the text to support efficient on-line pattern queries. We study this problem in the case where the text is weighted: for every position of the text and every letter of the alphabet a probability of occurrence of this letter at this position is given. Sequences of this type, also called position weight matrices, are commonly used to represent imprecise or uncertain data. A weighted sequence may represent many different strings, each with probability of occurrence equal to the product of probabilities of its letters at subsequent positions. Given a probability threshold $1/z$, we say that a pattern string $P$ matches a weighted text at position $i$ if the product of probabilities of the letters of $P$ at positions $i,\ldots,i+|P|-1$ in the text is at least $1/z$. In this article, we present an $O(nz)$-time construction of an $O(nz)$-sized index that can answer pattern matching queries in a weighted text in optimal time improving upon the state of the art by a factor of $z \log z$. Other applications of this data structure include an $O(nz)$-time construction of the weighted prefix table and an $O(nz)$-time computation of all covers of a weighted sequence, which improve upon the state of the art by the same factor.

Longest common extension queries (often called longest common prefix queries) constitute a fundamental building block in multiple string algorithms, for example computing runs and approximate pattern matching. We show that a sequence of q LCE queries for a string of size n over a general ordered alphabet can be realized in O(q log log n + n log* n) time making only O(q + n) symbol comparisons. Consequently, all runs in a string over a general ordered alphabets can be computed in O(n log log n) time making O(n) symbol comparisons. Our results improve upon a solution by Kosolobov (Information Processing Letters, 2016), who designed an algorithm with O(n log^⅔ n) running time and conjectured that O(n) time is possible. Our paper makes a significant progress towards resolving this conjecture. Our techniques extend to the case of general unordered alphabets, when the time increases to O(q log n + n log* n). The main tools are difference covers and a variant of the disjoint-sets data structure by La Poutré (SODA 1990).

For a text given in advance, the substring minimal suffix queries ask to determine the lexicographically minimal non-empty suffix of a substring specified by the location of its occurrence in the text. We develop a data structure answering such queries optimally: in constant time after linear-time preprocessing. This improves upon the results of Babenko et al. (CPM 2014), whose trade-off solution is characterized by $Θ(n\log n)$ product of these time complexities. Next, we extend our queries to support concatenations of $O(1)$ substrings, for which the construction and query time is preserved. We apply these generalized queries to compute lexicographically minimal and maximal rotations of a given substring in constant time after linear-time preprocessing. Our data structures mainly rely on properties of Lyndon words and Lyndon factorizations. We combine them with further algorithmic and combinatorial tools, such as fusion trees and the notion of order isomorphism of strings.

In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hüffner et al. (Theory Comput. Syst. 47(1), 196–217, 2010) initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant $\mathcal {O}\left (\min (2^{k} k^{6} \log k + n^{3}, 2^{k} km\sqrt {n} \log n)\right )$ -time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for Cluster Vertex Deletion and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2 k -barrier for Cluster Vertex Deletion and present an $\mathcal {O}(1.9102^{k} (n+m))$ -time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm’s branching steps.

We give efficient algorithms for ranking Lyndon words of length $n$ over an alphabet of size $\sigma$. The rank of a Lyndon word is its position in the sequence of lexicographically ordered Lyndon words of the same length. The outputs are integers of exponential size, and complexity of arithmetic operations on such large integers cannot be ignored. Our model of computations is the word RAM, in which basic arithmetic operations on (large) numbers of size at most $\sigma^n$ take $\mathcal{O}(n)$ time. Our algorithm for ranking Lyndon words makes $O(n^2)$ arithmetic operations (this would imply directly cubic time on word RAM). However, using an algebraic approach we are able to reduce the total time complexity on word RAM to $O(n^2 \log\sigma)$. We also present an $O(n^3 \log^2 \sigma)$-time algorithm that generates the Lyndon word of a given length and rank in lexicographic order. Finally we use the connections between Lyndon words and lexicographically minimal de Bruijn sequences (a theorem of Fredricksen and Maiorana) to develop the first polynomial-time algorithm for decoding the minimal de Bruijn sequence of any rank $n$ (it determines the position of a given word of length $n$ within the de Bruijn sequence).

In the Upper Degree-Constrained Partial Orientation (UDPO) problem we are given an undirected graph G=(V,E), together with two degree constraint functions d^-,d^+:V -> N. The goal is to orient as many edges as possible, in such a way that for each vertex v in V the number of arcs entering v is at most d^-(v), whereas the number of arcs leaving v is at most d^+(v). This problem was introduced by Gabow [SODA'06], who proved it to be MAXSNP-hard (and thus APX-hard). In the same paper Gabow presented an LP-based iterative rounding 4/3-approximation algorithm. As already observed by Gabow, the problem in question is a special case of the classic 3-Dimensional Matching, which in turn is a special case of the k-Set Packing problem. Back in 2006 the best known polynomial time approximation algorithm for 3-Dimensional Matching was a simple local search by Hurkens and Schrijver [SIDMA'89], the approximation ratio of which is (3+epsilon)/2; hence the algorithm of Gabow was an improvement over the approach brought from the more general problems. In this paper we show that the UDPO problem when cast as 3-Dimensional Matching admits a special structure, which is obliviously exploited by the known approximation algorithms for k-Set Packing. In fact, we show that already the local-search routine of Hurkens and Schrijver gives (4+epsilon)/3-approximation when used for the instances coming from UDPO. Moreover, the recent approximation algorithm for 3-Set Packing [Cygan, FOCS'13] turns out to be a (5+epsilon)/4-approximation for UDPO. This improves over 4/3 as the best ratio known up to date for UDPO.

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size σ ≤ n, our method builds the wavelet tree in time, improving upon the state-of-the-art algorithm by a factor of . As a consequence, given an array of n integers we can construct in time a data structure consisting of (n) machine words and capable of answering rank/select queries for the subranges of the array in (log n/log log n) time. This is a log log n-factor improvement in query time compared to Chan and Pâtraşcu (SODA 2010) and a -factor improvement in construction time compared to Brodal et al. (Theor. Comput. Sci. 2011). Next, we switch to stringological context and propose a novel notion of wavelet suffix trees. For a string w of length n, this data structure occupies (n) words, takes time to construct, and simultaneously captures the combinatorial structure of substrings of w while enabling efficient top-down traversal and binary search. In particular, with a wavelet suffix tree we are able to answer in (log |x|) time the following two natural analogues of rank/select queries for suffixes of substrings: 1.1) For substrings x and y of w (given by their endpoints) count the number of suffixes of x that are lexicographically smaller than y;2.2) For a substring x of w (given by its endpoints) and an integer k, find the k-th lexicographically smallest suffix of x. We further show that wavelet suffix trees allow to compute a run-length-encoded Burrows-Wheeler transform of a substring X of w (again, given by its endpoints) in (s log |x|) time, where s denotes the length of the resulting run-length encoding. This answers a question by Cormode and Muthukrishnan (SODA 2005), who considered an analogous problem for Lempel-Ziv compression. All our algorithms, except for the construction of wavelet suffix trees, which additionally requires (n) time in expectation, are deterministic and operate in the word RAM model.

We consider several types of internal queries: questions about subwords of a text. As the main tool we develop an optimal data structure for the problem called here internal pattern matching. This data structure provides constant-time answers to queries about occurrences of one subword x in another subword y given text, assuming that , which allows for a constant-space representation of all occurrences. This problem can be viewed as a natural extension of the well-studied pattern matching problem. The data structure has linear size and admits a linear-time construction algorithm. Using the solution to the internal pattern matching problem, we obtain very efficient data structures answering queries about: primitivity of subwords, periods of subwords, general substring compression, and cyclic equivalence of two subwords. All these results improve upon the best previously known counterparts. The linear construction time of our data structure also allows to improve the algorithm for finding δ-subrepetitions in a text (a more general version of maximal repetitions, also called runs). For any fixed δ we obtain the first linear-time algorithm, which matches the linear time complexity of the algorithm computing runs. Our data structure has already been used as a part of the efficient solutions for subword suffix rank & selection, as well as substring compression using Burrows-Wheeler transform composed with run-length encoding. The model of internal queries in texts is connected to the well-studied problem of text indexing. Both models have their origins in the introduction of suffix trees. However, there is an important difference: in our model the size of the representation of a query is constant and therefore enables faster query time. Our results can be viewed as efficient solutions to “internal” equivalents of several basic problems of regular pattern matching and make an improvement in a majority of already published results related to internal queries.

A factor $$u$$ of a word $$w$$ is a cover of $$w$$ if every position in $$w$$ lies within some occurrence of $$u$$ in $$w$$ . A word $$w$$ covered by $$u$$ thus generalizes the idea of a repetition, that is, a word composed of exact concatenations of $$u$$ . In this article we introduce a new notion of $$\alpha $$ -partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least $$\alpha $$ positions in $$w$$ . We develop a data structure of $$\mathcal {O}(n)$$ size (where $$n=|w|$$ ) that can be constructed in $$\mathcal {O}(n\log n)$$ time which we apply to compute all shortest $$\alpha $$ -partial covers for a given $$\alpha $$ . We also employ it for an $$\mathcal {O}(n\log n)$$ -time algorithm computing a shortest $$\alpha $$ -partial cover for each $$\alpha =1,2,\ldots ,n$$ .

The k-center problem is a classic facility location problem, where given an edge-weighted graph G=(V,E) one is to find a subset of k vertices S, such that each vertex in V is "close" to some vertex in S. The approximation status of this basic problem is well understood, as a simple 2-approximation algorithm is known to be tight. Consequently different extensions were studied. In the capacitated version of the problem each vertex is assigned a capacity, which is a strict upper bound on the number of clients a facility can serve, when located at this vertex. A constant factor approximation for the capacitated k-center was obtained last year in [Cygan, Hajiaghayi and Khuller, FOCS'12], which was recently improved to a 9-approximation in [An, Bhaskara and Svensson, arXiv'13]. In a different generalization of the problem some clients (denoted as outliers) may be disregarded. Here we are additionally given an integer p and the goal is to serve exactly p clients, which the algorithm is free to choose. In [Charikar et al., SODA'01] the authors presented a 3-approximation for the k-center problem with outliers. In this paper we consider a common generalization of the two extensions previously studied separately, i.e. we work with the capacitated k-center with outliers. We present the first constant factor approximation algorithm with approximation ratio of 25 even for the case of non-uniform hard capacities.

We present efficient algorithms computing all Abelian periods of two types in a word. Regular Abelian periods are computed in O(n log log{n}) randomized time which improves over the best previously known algorithm by almost a factor of n. The other algorithm, for full Abelian periods, works in O(n) time. As a tool we develop an O(n) time construction of a data structure that allows O(1) time gcd(i,j) queries for all 1 <= i,j <= n, this is a result of independent interest.

A seed in a word is a relaxed version of a period. We show a linear time algorithm computing a compact representation of all the seeds of a word, in particular, the shortest seed. Thus, we solve an open problem stated in the survey by Smyth (2000) and improve upon a previous over 15-year old O(n log n) algorithm by Iliopoulos, Moore and Park (1996). Our approach is based on combinatorial relations between seeds and a variant of the LZ-factorization (used here for the first time in context of seeds).