Pattern Matching under Weighted Edit Distance

In Pattern Matching with Weighted Edits (PMwWE), we are given a pattern P of length m, a text T of length n, a positive threshold k, and oracle access to a weight function that specifies the costs of edits (depending on the involved characters, and normalized so that the cost of each edit is at least 1). The goal is to compute the starting positions of all fragments of T that can be obtained from P with edits of total cost at most k. PMwWE captures typical real-world applications more accurately than its unweighted variant (PMwE), where all edits have unit costs.Indeed, the textbook $\mathcal{O}\left( {nm} \right)$-time algorithm of Sellers [J. Algorithms'80], devised in the context of bioinformatics, already accounts for weights. Surprisingly, the understanding of PMWWE has not advanced in the last 45 years. In contrast, significant milestones for PMwE include an $\mathcal{O}\left( {nk} \right)$-time algorithm by Landau and Vishkin [STOC'86, J. Algorithms'89], an $\mathcal{O}(n + {k^4} \cdot n/m)$-time algorithm by Cole and Hariharan [SODA'98, SICOMP'02], and a recent $\tilde {\mathcal{O}}(n + {k^{3.5}} \cdot n/m)$-time solution by Charalampopoulos, Kociumaka, and Wellnitz [FOCS'22].In this work, we examine whether these results can be lifted to PMWWE even though (1) the underlying algorithms rely on combinatorial properties specific to the unweighted edit distance, and (2) under standard fine-grained complexity assumptions, computing the weighted edit distance is strictly harder than computing the unweighted edit distance [Cassis, Kociumaka, and Wellnitz; FOCS'23]. We obtain three main results:•a conceptually simple $\tilde {\mathcal{O}}\left( {nk} \right)$-time algorithm for PMWWE, very different from that of Landau and Vishkin;•a significantly more complicated $\tilde {\mathcal{O}}(n + {k^{3.5}} \cdot {W^4} \cdot n/m)$ time algorithm for PMWWE under the assumption that the weight function is a metric with integer values between 0 and W; and•an $\tilde {\mathcal{O}}(n + {k^4} \cdot n/m)$-time algorithm for PMWWE for the case of arbitrary weights. In the setting of metrics with small integer values, we nearly match the state of the art for PMwE where W=1.