Faster Sublinear-Time Edit Distance
Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka · Society for Industrial and Applied Mathematics eBooks · 2024
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable shift in focus towards sublinear-time algorithms. Here, the task is typically formalized as the (k, K)-gap edit distance problem: Distinguish whether the edit distance of two strings is at most k or more than K.