In this work, we study periodicity in strings with wildcards. A string T with at most k wildcards is called strongly (p,k)-periodic if the wildcards in T can be replaced with alphabet symbols to obtain a string with period p, and weakly (p,k)-periodic if T[i] matches T[i+p] for all i. Intuitively, both generalize to (≤ g, k)-periodicity, which is the property of being (p,k)-periodic for some p ∈ [1..g]. An ε-tester for a property 𝒫 is an algorithm that distinguishes between strings that satisfy 𝒫 and strings where one needs to change at least an ε-fraction of the symbols to obtain a string that satisfies 𝒫. We study one-sided error testers, where strings satisfying 𝒫 must always be accepted, while strings that are ε-far must be rejected with probability at least 2/3. The complexity of a tester is the worst-case number of symbols of an input of length n it must read to make the decision. We design the following testers for p,g ≤ n/2: 1) An ε-tester for strong (p,k)-periodicity with complexity Õ_ε(1) . 2) An ε-tester for strong (≤ g,k)-periodicity with complexity Õ_ε(√g). 3) An ε-tester for weak (p,k)-periodicity with complexity Õ_ε(min(k, n /(k+p))). 4) An ε-tester for weak (≤ g,k)-periodicity with complexity Õ_ε(min(k+ √{gk}, n/√k)). Additionally, we show a lower bound on the complexity of ε-testers for weak (≤ g,k)-periodicity, implying that our tester for weak (≤ g,k)-periodicity is optimal up to a multiplicative (ε^{-1} ln(gk))^O(1) factor for a wide range of g and k. Finally, our tester for strong (≤ g,k)-periodicity generalizes the one of [Lachish and Newman; Algorithmica 2011] for strings without wildcards, matching (up to polylogarithmic factors) the unconditional lower bound of ̃Ω(√g) in said work for constant ε.

We study the space complexity of pattern matching in the asymmetric streaming model, focusing on approximate pattern matching under the Hamming and edit distances. In this problem, we are given an m-length pattern and an n-length text and must compute, for every position of the text, the smallest distance between the pattern and a substring of the text which ends at this position. In the asymmetric streaming model, we assume to have constant-time random access to the pattern, while the text arrives as a stream, one letter at a time. It is known that computing all distances exactly in the asymmetric streaming model requires Ω(m) space (for the edit distance see Li and Zheng [FSTTCS 2021]). Hence, to achieve sublinear space, a relaxation of the problem is necessary. One possible variant is to consider the small distance regime, where the algorithm must compute only those distances that are bounded by a small integer parameter k. In this case, existing algorithms in a more restrictive fully streaming model (Kociumaka, Clifford, Porat [SODA'19], Bhattacharya, Koucký [ICALP'23]) straightforwardly imply the existence of poly(k, log n)-space asymmetric streaming algorithms. Another possible relaxation is computing all distances approximately. For this variant, we don't have small-space algorithms in the fully streaming model: the best known algorithm solves pattern matching under the Hamming distance (1+ε)-approximately using 𝒪̃(ε^{-2}√m) space (Starikovskaya, Svagerka, Uznański [APPROX'20]). For the edit distance, no efficient approximation algorithms are known. In this work, we show approximation algorithms for pattern matching under the Hamming and edit distances in the asymmetric streaming model for any constant ε > 0: 1) We show that there is a simple randomised asymmetric streaming algorithm that solves approximate pattern matching under the Hamming distance (1+ε)-approximately using 𝒪(ε^{-3}log³n) bits. 2) As our second and main contribution, we extend the result of Cheng et al. [ICALP 2021] and show that for any integer k there is a deterministic asymmetric streaming algorithm that solves pattern matching under the edit distance (2^k-1+ε)-approximately using 𝒪̃(m^{1/k}) space.

In approximate circular pattern matching the goal is to compute all approximate occurrences of all rotations of a pattern P in a text T. We study this problem under the two most fundamental string distance metrics, the Hamming distance and the edit distance, in the setting where the text arrives online and the available space is limited. Specifically, we wish to report each ending position j of an approximate occurrence before symbol T[j+1] arrives, using sublinear space on top of having read-only access to P and (the seen prefix of) T. For both variants, we present algorithms that use O(poly(k)) extra space and process each arriving symbol in O(poly(k)) time. Notably, with an overhead, our algorithms can be lifted to the asymmetric streaming setting, where we only have read-only access to the pattern for free and account for all extra space.

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model (see also [Andoni, Krauthgamer, and Onak; FOCS 2010]). Here, one is given read-only access to a (typically short) reference string R of length m, while a (typically long) text T arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression, a popular scheme for measuring and exploiting redundancy in repetitive text collections. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) T that occurs in R. Let τ be a parameter that denotes the size of the data structure. A straightforward approach maintains the data structure in {O}(m/τ) time per arriving symbol of T. We drastically improve this tradeoff and reveal fundamental barriers via a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography: - By leveraging Fiat and Naor’s function inversion data structure [SIAM J. Comput. 2000], we achieve Õ(1+m³/τ⁶) update time. In particular, for τ = √m, we obtain Õ(1) update time, improving over the Ω(√m) bound of the straightforward solution. - We establish an unconditional Ω̃(m/τ³) lower bound on the update time. Additionally, we show that achieving update time o(m³/τ⁷) would imply a breakthrough in function inversion. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.

The Dyck language, consisting of well-balanced parenthesis sequences, is one of the central objects in formal language theory. The Dyck languages appear naturally in numerous applications: balanced-parenthesis encodings succinctly represent rooted trees, programming languages rely heavily on nested structures, and structured data formats such as XML often utilize a notion of balanced parenthesis sequences. Dyck languages also arise in computational biology. RNA and DNA secondary structures can often be viewed as "almost balanced" sequences, so understanding the behaviour of the Dyck languages is often an important building block for designing algorithms on such sequences. In this talk, I will survey several recent developments in Dyck language recognition, highlighting surprising connections to different areas of TCS, including regular language recognition, Boolean matrix multiplication, pattern matching, and graph algorithms. I will also discuss some of the major open questions in the area.

A walk of length n on a string S of length m is a function f : {1, … , n} → {1, … , m} such that ∀ i ∈ {2, … , n} : |f(i) - f(i - 1)| ≤ 1. The walk generates the string T of length n defined by {∀ i ∈ {1, … , n} : T[i] = S[f(i)]}. Intuitively, this can be seen as walking n steps in S and outputting the encountered symbols, where in each step we either remain at the same position, or move one position to the left or to the right. The minimal generator of a string T is the shortest string S such that a walk on S generates T. Recently, it was shown that each string admits exactly one (up to reversal) minimal generator (Pratt-Hartmann, CPM 2024). However, no efficient algorithm for computing the minimal generator was known. We provide an optimal algorithm for this task, taking {O}(n) time for a string of length n over general unordered alphabet, i.e., accessing the string only by equality comparisons of symbols. The main challenge is to detect substrings of the form axbx̃axb and replace them with axb, where a,b are symbols and x is a string with reversal x̃. We solve this problem with a non-trivial adaptation of Manacher’s classic algorithm for computing maximal palindromic substrings (Manacher, J. ACM 1975). To obtain the final algorithm, we solve small subinstances of the problem in optimal time by adapting the "Four Russians" technique to strings over general unordered alphabet, which may be of independent interest.

In this work, we study the problem of detecting periodic trends in strings. While detecting exact periodicity has been studied extensively, real-world data is often noisy, where small deviations or mismatches occur between repetitions. This work focuses on a generalized approach to period detection that efficiently handles noise. Given a string S of length n, the task is to identify integers p such that the prefix and the suffix of S, each of length n-p+1, are similar under a given distance measure. Ergün et al. [APPROX-RANDOM 2017] were the first to study this problem in the streaming model under the Hamming distance. In this work, we combine, in a non-trivial way, the Hamming distance sketch of Clifford et al. [SODA 2019] and the structural description of the k-mismatch occurrences of a pattern in a text by Charalampopoulos et al. [FOCS 2020] to present a more efficient streaming algorithm for period detection under the Hamming distance. As a corollary, we derive a streaming algorithm for detecting periods of strings which may contain wildcards, a special symbol that match any character of the alphabet. Our algorithm is not only more efficient than that of Ergün et al. [TCS 2020], but it also operates without their assumption that the string must be free of wildcards in its final characters. Additionally, we introduce the first two-pass streaming algorithm for computing periods under the edit distance by leveraging and extending the Bhattacharya-Koucký’s grammar decomposition technique [STOC 2023].

The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters. Due to the potential practical applications, it is desirable to seek approximate occurrences, for example by bounding the number of mismatches. This problem has been extensively studied, and by now we have a good understanding of the best possible time complexity as a function of n (length of the text), m (length of the pattern), and k (number of mismatches). In particular, we know that for , we can achieve quasi-linear time complexity [Gawrychowski and Uznański, ICALP 2018].

Originating from the work of Navarro and Thankachan [TCS 2016], the problem of consecutive pattern matching is a variant of the fundamental pattern matching problem, where one is given a text and a pair of patterns, and must compute their consecutive occurrences in the text. Assuming that the text is given as a straight-line program, we develop an algorithm that computes all consecutive occurrences in optimal time.

International audience

International audience

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.

International audience

International audience

Regular expression search is a key primitive in myriads of applications, from web scrapping to bioinformatics. A regular expression is a formalism for compactly describing a set of strings, built recursively from single characters using three operators: concatenation, union, and Kleene star. Two basic algorithmic problems concerning such expressions are membership and pattern matching. In the regular expression membership problem, we are given a regular expression R and a string T of length n, and must decide whether T matches R. In the regular expression pattern matching problem, the task to find the substrings of T that match R. By now we have a good understanding of the complexity of regular expression membership and pattern matching in the classical setting. However, only some special cases have been considered in the practically relevant streaming setting: dictionary matching and wildcard pattern matching. In the dictionary matching problem, we are given a dictionary of d strings of length at most m and a string T, and must find substrings of T that match one of the dictionary strings. In the wildcard pattern matching problem, we are given a string P of length m that contains d wildcards, where a wildcard is a special symbol that matches any character of the alphabet, and a string T, and must find all substrings of T that match P. Both problems can be solved in the streaming model by a randomised Monte Carlo algorithm that uses (d log m) space [Golan and Porat (ESA 2017), Golan, Kopelowitz and Porat (Algorithmica 2019)]. In the general case, we cannot hope for a streaming algorithm with space complexity smaller than the length of R for either variant of regular expression search. The main contribution of this paper is that we identify the number of unions and Kleene stars, denoted by d, as the parameter that allows for an efficient streaming algorithm. This parameter has been previously considered in the classical setting, and it has been observed that in practice it is significantly smaller than the length of R. We design general randomised Monte Carlo algorithms for both problems that use (d3 polylog n) space in the streaming setting. A crucial technical ingredient of our algorithms is an adaptation of the general framework for evaluating a circuit with addition and convolution gates in a space-efficient manner [Lokshtanov and Nederlof (STOC 2010), Bringmann (SODA 2017)], initially designed as a key component of a pseudopolynomial time algorithm for the subset sum problem. We show how to replace the Extended Generalised Riemann Hypothesis in [Bringmann (SODA 2017)] by an application of the Bombieri–Vinogradov theorem to achieve the same bounds (but unconditionally), which might be of independent interest.

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.

In the k-mismatch problem we are given a pattern of length n and a text and must find all locations where the Hamming distance between the pattern and the text is at most k. A series of recent breakthroughs have resulted in an ultra-efficient streaming algorithm for this problem that requires only $$\mathcal {O}(k \log \frac{n}{k})$$ space and $$\mathcal {O}(\log \frac{n}{k} (\sqrt{k \log k} + \log ^3 n))$$ time per letter (Clifford, Kociumaka, Porat, SODA 2019). In this work, we consider a strictly harder problem called dictionary matching with k mismatches. In this problem, we are given a dictionary of d patterns, where the length of each pattern is at most n, and must find all substrings of the text that are within Hamming distance k from one of the patterns. We develop a streaming algorithm for this problem with $$\mathcal {O}(k d \log ^k d \mathop {\mathrm {polylog} {\,n}})$$ space and $$\mathcal {O}(k \log ^{k} d \mathop {\mathrm {polylog} {\,n}} + |\mathrm {output}|)$$ time per position of the text. The algorithm is randomised and outputs correct answers with high probability. On the lower bound side, we show that any streaming algorithm for dictionary matching with k mismatches requires $$\varOmega (k d)$$ bits of space.

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].

In this work, we revisit the problem of testing membership in regular languages, first studied by Alon et al. [Alon et al., 2001]. We develop a one-sided error property tester for regular languages under weighted edit distance that makes 𝒪(ε^{-1} log(1/ε)) non-adaptive queries, assuming that the language is described by an automaton of constant size. Moreover, we show a matching lower bound, essentially closing the problem for the edit distance. As an application, we improve the space bound of the current best streaming property testing algorithm for visibly pushdown languages from 𝒪(ε^{-4} log⁶ n) to 𝒪(ε^{-3} log⁵ n log log n), where n is the size of the input. Finally, we provide a Ω(max(ε^{-1}, log n)) lower bound on the memory necessary to test visibly pushdown languages in the streaming model, significantly narrowing the gap between the known bounds.

Many classical algorithms for string processing assume that the input can be accessed in full via constant-time random access, which poses a serious limitation in the modern era of data deluge. In this talk, we will focus on the streaming model of computation that allows to overcome this issue. In this model of computation, we assume that the input arrives as a stream, one character at a time, which captures a situation when the data are sequential measurements or an output of an algorithm. The space complexity is defined as all the space used, including the space used to store any information about the input, which allows to develop ultra-efficient algorithms. The first streaming algorithm for pattern matching was presented in the seminal paper of Porat and Porat in FOCS 2009. For a pattern of length m, the algorithm uses only O(log m) space, while any classical algorithm requires Ω(m) space. This result served as a foundation of the area of streaming algorithms for pattern matching. After a brief survey of the area, we will discuss two questions in more details: the k-mismatch problem and the pattern matching with k-edits problem. In the k-mismatch problem, one is given a pattern and a text, and the task is to find all substrings of the text that have at most k mismatches with the pattern. The current best algorithm for this problem was given by Clifford, Kociumaka, and Porat in SODA 2019, and for a pattern of length m it uses O(k log m) space and Õ(√k) time per character of the text. In the pattern matching with k-edits problem, the task is similar, but one must find substrings that can be transformed into the pattern by at most k edits, i.e. substitutions, insertions, and deletions of a character. For this problem, the first streaming algorithm was presented by Kociumaka, Porat, and Starikovskaya in FOCS 2021. The algorithm takes Õ(poly(k)) space and Õ(poly(k)) time per character of the text.

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.

In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukrishnan and Palem], we are given a text T of length n over an alphabet Σ_T, a pattern P of length m over an alphabet Σ_P, and a matching relationship ⊆ Σ_T × Σ_P, and must return all substrings of T that match P (reporting) or the number of mismatches between each substring of T of length m and P (counting). In this work, we improve over all previously known algorithms for this problem: - For ? being the maximum number of characters that match a fixed character, we show two new Monte Carlo algorithms, a reporting algorithm with time ?(? n log n log m) and a (1-ε)-approximation counting algorithm with time ?(ε^-1 ? n log n log m). We then derive a (1-ε)-approximation deterministic counting algorithm for GPM with ?(ε^-2 ? n log⁶ n) time. - For ? being the number of pairs of matching characters, we demonstrate Monte Carlo algorithms for reporting and (1-ε)-approximate counting with running time ?(√? n log m √{log n}) and ?(√{ε^-1 ?} n log m √{log n}), respectively, as well as a (1-ε)-approximation deterministic algorithm for the counting variant of GPM with ?(ε^-1 √{?} n log^{7/2} n) time. - Finally, for ℐ being the total number of disjoint intervals of characters that match the m characters of the pattern P, we show that both the reporting and the counting variants of GPM can be solved exactly and deterministically in ?(n√{ℐ log m} +n log n) time. At the heart of our new deterministic upper bounds for ? and ? lies a faster construction of superimposed codes, which solves an open problem posed in [FOCS'97, Indyk] and can be of independent interest. To conclude, we demonstrate first lower bounds for GPM. We start by showing that any deterministic or Monte Carlo algorithm for GPM must use Ω(?) time, and then proceed to show higher lower bounds for combinatorial algorithms. These bounds show that our algorithms are almost optimal, unless a radically new approach is developed.

The popular 3-SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements that sum up to zero. A closely related problem is to check if a given set of integers contains distinct x 1, x 2, x 3 such that x 1+x 2=2x 3. This can be reduced to 3-SUM in almost-linear time, but surprisingly a reverse reduction establishing 3-SUM hardness was not known.

In this work, we show two streaming algorithms for computing the length of the shortest cover of a string of length n. We start by showing a two-pass algorithm that uses O(log^2 n) space and then show a one-pass streaming algorithm that uses O(sqrt{n log n}) space. Both algorithms run in near-linear time. The algorithms are randomized and compute the answer incorrectly with probability inverse-polynomial in n. We also show that there is no sublinear-space streaming algorithm for computing the length of the shortest seed of a string.

We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window $n$ and a stream of symbols. At each time instant, we must decide whether the suffix of length $n$ of the current stream ("the active window") belongs to a given regular language. Recent works showed that the space complexity of an optimal deterministic sliding window algorithm for this problem is either constant, logarithmic or linear in the window size $n$ and provided natural language theoretic characterizations of the space complexity classes. Subsequently, those results were extended to randomized algorithms to show that any such algorithm admits either constant, double logarithmic, logarithmic or linear space complexity. In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length n, the “text”, and the task is to preprocess it into a data structure such that given a query string Q, one can quickly identify substrings that are within Hamming or edit distance at most k from Q. This problem is at the core of various problems arising in biology and text processing. While exact text indexing allows linear-size data structures with linear query time, text indexing with k mismatches (or k differences) seems to be much harder: All known data structures have exponential dependency on k either in the space, or in the time bound. We provide conditional and pointer-machine lower bounds that make a step toward explaining this phenomenon. We start by demonstrating lower bounds for k = Θ(log n). We show that assuming the Strong Exponential Time Hypothesis, any data structure for text indexing that can be constructed in polynomial time cannot have O(n1–δ) query time, for any δ > 0. This bound also extends to the setting where we only ask for (1 + ε)-approximate solutions for text indexing. However, in many applications the value of k is rather small, and one might hope that for small k we can develop more efficient solutions. We show that this would require a radically new approach as using the current methods one cannot avoid exponential dependency on k either in the space, or in the time bound for all even . Our lower bounds also apply to the dictionary look-up problem, where instead of a text one is given a set of strings.

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 revisit the fundamental problem of dictionary look-up with mismatches. Given a set (dictionary) of $d$ strings of length $m$ and an integer $k$, we must preprocess it into a data structure to answer the following queries: Given a query string $Q$ of length $m$, find all strings in the dictionary that are at Hamming distance at most $k$ from $Q$. Chan and Lewenstein (CPM 2015) showed a data structure for $k = 1$ with optimal query time $O(m/w + occ)$, where $w$ is the size of a machine word and $occ$ is the size of the output. The data structure occupies $O(w d \log^{1+\varepsilon} d)$ extra bits of space (beyond the entropy-bounded space required to store the dictionary strings). In this work we give a solution with similar bounds for a much wider range of values $k$. Namely, we give a data structure that has $O(m/w + \log^k d + occ)$ query time and uses $O(w d \log^k d)$ extra bits of space.

In this paper we consider the problem of deciding membership in Dyck languages, a fundamental family of context-free languages, comprised of well-balanced strings of parentheses. In this problem we are given a string of length n in the alphabet of parentheses of m types and must decide if it is well-balanced. We consider this problem in the property testing setting, where one would like to make the decision while querying as few characters of the input as possible. Property testing of strings for Dyck language membership for m = 1, with a number of queries independent of the input size n, was provided in [Alon, Krivelevich, Newman and Szegedy, SICOMP 2001]. Property testing of strings for Dyck language membership for m ≥ 2 was first investigated in [Parnas, Ron and Rubinfeld, RSA 2003]. They showed an upper bound and a lower bound for distinguishing strings belonging to the language from strings that are far (in terms of the Hamming distance) from the language, which are respectively (up to polylogarithmic factors) the 2/3 power and the 1/11 power of the input size n. Here we improve the power of n in both bounds. For the upper bound, we introduce a recursion technique, that together with a refinement of the methods in the original work provides a test for any power of n larger than 2/5. For the lower bound, we introduce a new problem called Truestring Equivalence, which is easily reducible to the 2-type Dyck language property testing problem. For this new problem, we show a lower bound of n to the power of 1/5.

We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length $m$ and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an $O(m^{1/2-\varepsilon})$ time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.

Suppose that we have two parties that possess each a binary string. Suppose that the length of the first string (document) is $n$ and that the two strings (documents) have edit distance (minimal number of deletes, inserts and substitutions needed to transform one string into the other) at most $k$. The problem we want to solve is to devise an efficient protocol in which the first party sends a single message that allows the second party to guess the first party's string. In this paper we show an efficient deterministic protocol for this problem. The protocol runs in time $O(n\cdot \mathtt{polylog}(n))$ and has message size $O(k^2+k\log^2n)$ bits. To the best of our knowledge, ours is the first efficient deterministic protocol for this problem, if efficiency is measured in both the message size and the running time. As an immediate application of our new protocol, we show a new error correcting code that is efficient even for large numbers of (adversarial) edit errors.

We present a new streaming algorithm for the k-Mismatch problem, one of the most basic problems in pattern matching. Given a pattern and a text, the task is to find all substrings of the text that are at the Hamming distance at most k from the pattern. Our algorithm is enhanced with an important new feature called Error Correcting, and its complexities for k = 1 and for a general k match those of the best known solutions for the k-Mismatch problem from FOCS 2009 and SODA 2016. As a corollary we develop a series of streaming algorithms for pattern matching on weighted strings, which are a commonly used representation of uncertain sequences in molecular biology.

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 letter. To circumvent this, Leimester 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, and several algorithms have been suggested. The running time of these algorithms is n^{2-o(1)}, and unfortunately, conditional lower bounds have been shown which imply that there is little hope to improve this bound. In this paper we study a different but closely related problem of the longest common substring with approximately k mismatches and use computational geometry techniques to show that it admits a randomised solution with strongly subquadratic running time.

We consider the problem of computing a (1+epsilon)-approximation of the Hamming distance between a pattern of length n and successive substrings of a stream. We first look at the one-way randomised communication complexity of this problem. We show the following: - If Alice and Bob both share the pattern and Alice has the first half of the stream and Bob the second half, then there is an O(epsilon^{-4}*log^2(n)) bit randomised one-way communication protocol. - If Alice has the pattern, Bob the first half of the stream and Charlie the second half, then there is an O(epsilon^{-2}*sqrt(n)*log(n)) bit randomised one-way communication protocol. We then go on to develop small space streaming algorithms for (1 + epsilon)-approximate Hamming distance which give worst case running time guarantees per arriving symbol. - For binary input alphabets there is an O(epsilon^{-3}*sqrt(n)*log^2(n)) space and O(epsilon^{-2}*log(n)) time streaming (1 + epsilon)-approximate Hamming distance algorithm. - For general input alphabets there is an O(epsilon^{-5}*sqrt(n)*log^4(n)) space and O(epsilon^{-4}*log^3(n)) time streaming (1 + epsilon)-approximate Hamming distance algorithm.

We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output “No”. We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows: Our first result is a deterministic O(nk2 log k/m + n polylog m) time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000 [9, 10]. We then give a randomised and online algorithm which runs in the same time complexity but requires only O(k2 polylog m) space in total. Next we give a randomised (1 + ∊)-approximation algorithm for the streaming k-mismatch problem which uses O(k2 polylog m/∊2) space and runs in O(polylog m/∊2) worst-case time per arriving symbol. Finally we combine our new results to derive a randomised O(k2 polylog m) space algorithm for the streaming k-mismatch problem which runs in worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 [26] by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).

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.