Faster Approximate Pattern Matching: A Unified Approach
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz · 2020
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.