An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings

2024/11/14 by Rao Li, Li, Rao
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #DNA and Biological Computing

paper · pdf · doi:10.48550/arxiv.2411.09472

Abstract

Let X₁, X₂, ..., X_s and Y₁, Y₂, ..., Y_t be strings over an alphabet Σ, where s and t are positive integers. The longest common subsequence and substring problem for multiple strings X₁, X₂, ..., X_s and Y₁, Y₂, ..., Y_t is to find the longest string which is a subsequence of X₁, X₂, ..., X_s and a substring of Y₁, Y₂, ..., Y_t. In this paper, we propose an algorithm to solve the problem.

Related

• An Algorithm for the Longest Common Subsequence and Substring Problem
• An Algorithm for the Constrained Longest Common Subsequence and Substring Problem
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings
• Efficient algorithms for the longest common subsequence in k-length substrings
• Faster Algorithms for Longest Common Substring