Faster Approximate Pattern Matching: A Unified Approach

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 | < |T | ≤ 3 / 2 |P | and that P occurs both as a prefix and as a suffix of T , then both P and T are periodic with a common period. However, an analogous characterization for occurrences with up to k mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are O(k 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-error occurrences by O(k 2 ) in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching with respect to 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 following settings:

The fully compressed setting, where both T and P are given as straight-line programs of sizes n and m, respectively. Here, we obtain an Õ((n + m)k 2 )-time and an Õ((n + m)k 4 )-time algorithm for pattern matching with mismatches and edits, respectively. Note that while our algorithms are the first to work in the fully compressed setting (that is, without first decompressing the input), they also improve the state of the art for the setting where only the text is compressed: For pattern matching with mismatches, we improve the dependency on k from Õ((n + |P |)k 4 ) [Bringmann et al. SODA'19]; for pattern matching with edits, we improve the overall running time from Õ(n

The dynamic setting, where we maintain a collection of strings X of total length N using the data structure of Gawrychowski et al. [SODA'18], which supports each of the operations "split", "concatenate" and "insert a length-1 string" in O(log N ) time with high probability. Here, for any two strings T, P ∈ X , we can compute all occurrences of P in T with up to k mismatches in time Õ(|T |/|P | • k 2 ) or up to k edits in time Õ(|T |/|P | • k 4 ). The standard setting, where T and P are given explicitly. Here, we obtain an O(|T | + |T |/|P | • k 2 log log k)-time algorithm for the Hamming distance case (improving polylog |T | factors compared to the deterministic algorithm by Clifford et al. [SODA'18] and matching, up to the log log k factor, the randomized algorithm by Chan et al. [STOC'20], the state of the art for k ≤ |P |), and an O(|T | + |T |/|P | • k 4 )-time algorithm for the edit distance case (matching the algorithm by Cole and Hariharan [J. Comput.'02], the state of the art for k ≤ 3 |P |).