Faster Approximate Pattern Matching: A Unified Approach

Exact occurrences of P in T have a very simple structure: If we assume for simplicity that |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 the structure of occurrences with up to k mismatches was proved only recently by Bringmann et al. [SODA’19]: Either there are O(k²) k-mismatch occurrences of P in T, or both P and T are at Hamming distance O(k) from strings with a common period O(m/k). We tighten this characterization by showing that there are O(k) k-mismatch occurrences in the case when the pattern is not (approximately) periodic, and we lift it to the edit distance setting, where we tightly bound the number of k-edit occurrences by O(k²) 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 crucial primitive operations (such as identifying the longest common prefix of two substrings). We showcase the generality of our meta-algorithms with results for the fully-compressed setting, the dynamic setting, and the standard setting.

(Joint work with Panagiotis Charalampopoulos and Tomasz Kociumaka.)

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.