Approximating longest common substring with k mismatches: Theory and practice

2020/04/28 by Garance Gourdel, Gourdel, Garance, Tomasz Kociumaka +5
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Wireless Communication Networks Research

paper · doi:10.48550/arxiv.2004.13389

openalex publication_date 2020/04/28 · openalex created_date 2020/07/02 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Longest common substring with approximately k mismatches
• A note on the longest common substring with k-mismatches problem
• An Algorithm for the Longest Common Subsequence and Substring Problem
• Longest Common Subsequence in k-length substrings
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings