Faster Pattern Matching under Edit Distance

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$ thatcan be transformed to $P$ with at most $k$ edits. More than 20 years ago, Coleand 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 beenimproved since. Here, we present an algorithm that runs in time $\mathcal{O}(n+k^{3.5}\sqrt{\log m \log k} \cdot n/m)$, thus breaking through this long-standingbarrier. In the case where $n^{1/4+\varepsilon} \leq k \leqn^{2/5-\varepsilon}$ for some arbitrarily small positive constant$\varepsilon$, our algorithm improves over the state-of-the-art by polynomialfactors: it is polynomially faster than both the algorithm of Cole andHariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau andVishkin [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 newalgorithm reduces this case to a new dynamic problem (Dynamic Puzzle Matching),which we solve by building on tools developed by Tiskin [SODA'10,Algorithmica'15] for the so-called seaweed monoid of permutation matrices. Ouralgorithm relies only on a small set of primitive operations on strings andthus also applies to the fully-compressed setting (where text and pattern aregiven as straight-line programs) and to the dynamic setting (where we maintaina collection of strings under creation, splitting, and concatenation),improving over the state of the art.