2026-07-23T12:38:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11010 2024-03-06T10:47:03Z ddc:004 open_access

RLE Edit Distance in Near Optimal Time Clifford, Raphaël Gawrychowski, Paweł Kociumaka, Tomasz Martin, Daniel P. Uznański, Przemysław String algorithms Compression Pattern matching Run-length encoding We show that the edit distance between two run-length encoded strings of compressed lengths m and n respectively, can be computed in O(mn log(mn)) time. This improves the previous record by a factor of O(n/log(mn)). The running time of our algorithm is within subpolynomial factors of being optimal, subject to the standard SETH-hardness assumption. This effectively closes a line of algorithmic research first started in 1993. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Raphaël Clifford and Paweł Gawrychowski and Tomasz Kociumaka and Daniel P. Martin and Przemysław Uznański 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.66 urn:nbn:de:0030-drops-110109 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.66 eng https://creativecommons.org/licenses/by/3.0/legalcode