Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task,...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/113874 https://orcid.org/0000-0001-7546-6313 https://orcid.org/0000-0002-7983-9524 |