On the Complexity of Finding Approximate LCS of Multiple Strings

2025/05/21 by Hamed Hasibi, Hasibi, Hamed, Neerja Mhaskar +3
Computer Science · #Algorithms and Data Compression #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition

paper · pdf · doi:10.48550/arxiv.2505.15992

openalex publication_date 2025/05/21 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

Finding an Approximate Longest Common Substring (ALCS) within a given set S=\s₁,s₂,…,s_m\ of m ≥ 2 strings is a key problem in computational biology, such as identifying related mutations across multiple genetic sequences. We study several variants of ALCS problems that, given integers k and t ≤ m, seek the longest string u -- or the longest substring u of any string in S -- that lies within distance k of at least one substring in t distinct strings from S. While the general problems are NP-hard, we present efficient algorithms for restricted cases under Hamming and edit distances using the LCP_k and k-errata tree data structures. Our methods achieve run times of O(N²), O(kℓ N²), and O(mNlog^k ℓ), where ℓ is the length of the longest string and N is the sum of the lengths of all the strings in S. We also establish conditional lower bounds under the Strong Exponential Time Hypothesis and extend our study to indeterminate strings.

Related

• Longest Common Subsequence in k-length substrings
• Efficient algorithms for the longest common subsequence in k-length substrings
• Faster Algorithms for Longest Common Substring
• Time-Space Tradeoffs for Finding a Long Common Substring
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings