Total: 1
The edit distance ed(X,Y) of two strings X,Y∈Σ∗ is the minimum number of character edits (insertions, deletions, and substitutions) needed to transform X into Y. Its weighted counterpart edw(X,Y) minimizes the total cost of edits, which are specified using a function w, normalized so that each edit costs at least one. The textbook dynamic-programming procedure, given strings X,Y∈Σ≤n and oracle access to w, computes edw(X,Y) in O(n2) time. Nevertheless, one can achieve better running times if the computed distance, denoted k, is small: O(n+k2) for unit weights [Landau and Vishkin; JCSS'88] and ˜O(n+√nk3) for arbitrary weights [Cassis, Kociumaka, Wellnitz; FOCS'23]. In this paper, we study the dynamic version of the weighted edit distance problem, where the goal is to maintain edw(X,Y) for strings X,Y∈Σ≤n that change over time, with each update specified as an edit in X or Y. Very recently, Gorbachev and Kociumaka [STOC'25] showed that the unweighted distance ed(X,Y) can be maintained in ˜O(k) time per update after ˜O(n+k2)-time preprocessing; here, k denotes the current value of ed(X,Y). Their algorithm generalizes to small integer weights, but the underlying approach is incompatible with large weights. Our main result is a dynamic algorithm that maintains edw(X,Y) in ˜O(k3−γ) time per update after ˜O(nkγ)-time preprocessing. Here, γ∈[0,1] is a real trade-off parameter and k≥1 is an integer threshold fixed at preprocessing time, with ∞ returned whenever edw(X,Y)>k. We complement our algorithm with conditional lower bounds showing fine-grained optimality of our trade-off for γ∈[0.5,1) and justifying our choice to fix k.