An Algorithm for the Longest Common Subsequence and Substring Problem

2023/08/02 by Li, R., Deka, J., Deka, K.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2308.00925

Abstract

In this note, we first introduce a new problem called the longest common subsequence and substring problem. Let X and Y be two strings over an alphabet Σ. The longest common subsequence and substring problem for X and Y is to find the longest string which is a subsequence of X and a substring of Y. We propose an algorithm to solve the problem.

Related

• An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
• An Algorithm for the Constrained Longest Common Subsequence and Substring Problem
• Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings
• Approximating longest common substring with k mismatches: Theory and practice
• Longest common substring with approximately k mismatches