October 20, 2025

An Algorithm for the Constrained Longest Common Subsequence and Substring Problem

Key Points

The proposed algorithm effectively solves the constrained longest common subsequence and substring problem.
It identifies a longest common string Z that adheres to conditions set by both strings X, Y and the constrained string P.
The algorithm enhances efficiency in string processing by addressing two critical problems simultaneously.
It provides a foundation for further developments in computational problems involving strings and subsequences.

Abstract

Let ∑ be an alphabet. For two strings X, Y, and a constrained string P over the alphabet ∑, the constrained longest common subsequence and substring problem for two strings X and Y with respect to P is to find a longest string Z which is a subsequence of X, a substring of Y, and has P as a subsequence. In this paper, we propose an algorithm for the constrained longest common subsequence and substring problem for two strings with a constrained string.

Ask AI

Helpful

Bookmark