2026-08-06T00:49:28Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:12141
2024-03-06T10:49:24Z
ddc:004
open_access
Approximating Longest Common Substring with k mismatches: Theory and Practice
Gourdel, Garance
Kociumaka, Tomasz
Radoszewski, Jakub
Starikovskaya, Tatiana
approximation algorithms
string similarity
LSH
conditional lower bounds
In the problem of the longest common substring with k mismatches we are given two strings X, Y and must find the maximal length π such that there is a length-π substring of X and a length-π substring of Y that differ in at most k positions. The length π can be used as a robust measure of similarity between X, Y. In this work, we develop new approximation algorithms for computing π that are significantly more efficient that previously known solutions from the theoretical point of view. Our approach is simple and practical, which we confirm via an experimental evaluation, and is probably close to optimal as we demonstrate via a conditional lower bound.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Garance Gourdel and Tomasz Kociumaka and Jakub Radoszewski and Tatiana Starikovskaya
2020
Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.CPM.2020.16
urn:nbn:de:0030-drops-121410
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.16
eng
https://creativecommons.org/licenses/by/3.0/legalcode