Weighted Edit Distance Computation: Strings, Trees and Dyck
Given two strings of length $n$ over alphabet $Σ$, and an upper bound $k$ on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88) computes the unweighted string edit distance in $\mathcal{O}(n+k^2)$ time. Till date, it remains the fastest algorithm for exact...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2302.04229 http://arxiv.org/abs/2302.04229 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|