On the generalized constrained longest common subsequence problems
YC Chen, KM Chao - Journal of Combinatorial Optimization, 2011 - Springer
We investigate four variants of the longest common subsequence problem. Given two
sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the …
sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the …
Approximating lcs in linear time: Beating the barrier
Longest common subsequence (LCS) is one of the most fundamental problems in
combinatorial optimization. Apart from theoretical importance, LCS has enormous …
combinatorial optimization. Apart from theoretical importance, LCS has enormous …
New efficient algorithms for the LCS and constrained LCS problems
CS Iliopoulos, MS Rahman - Information Processing Letters, 2008 - Elsevier
In this paper, we study the classic and well-studied longest common subsequence (LCS)
problem and a recent variant of it, namely the constrained LCS (CLCS) problem. In the …
problem and a recent variant of it, namely the constrained LCS (CLCS) problem. In the …
A new efficient algorithm for computing the longest common subsequence
CS Iliopoulos, MS Rahman - Theory of Computing Systems, 2009 - Springer
Abstract The Longest Common Subsequence (LCS) problem is a classic and well-studied
problem in computer science. The LCS problem is a common task in DNA sequence …
problem in computer science. The LCS problem is a common task in DNA sequence …
[HTML][HTML] Efficient algorithms for the longest common subsequence problem with sequential substring constraints
CT Tseng, CB Yang, HY Ann - Journal of Complexity, 2013 - Elsevier
In this paper, we generalize the inclusion constrained longest common subsequence
(CLCS) problem to the hybrid CLCS problem which is the combination of the sequence …
(CLCS) problem to the hybrid CLCS problem which is the combination of the sequence …
Constrained LCS: hardness and approximation
Z Gotthilf, D Hermelin, M Lewenstein - … , CPM 2008, Pisa, Italy, June 18-20 …, 2008 - Springer
The problem of finding the longest common subsequence (LCS) of two given strings A 1 and
A 2 is a well-studied problem. The constrained longest common subsequence (C-LCS) for …
A 2 is a well-studied problem. The constrained longest common subsequence (C-LCS) for …
Restricted lcs
Z Gotthilf, D Hermelin, GM Landau… - … Symposium on String …, 2010 - Springer
Abstract The Longest Common Subsequence (LCS) of two or more strings is a fundamental
well-studied problem which has a wide range of applications throughout computational …
well-studied problem which has a wide range of applications throughout computational …
Algorithms for computing variants of the longest common subsequence problem
CS Iliopoulos, MS Rahman - Theoretical Computer Science, 2008 - Elsevier
The longest common subsequence (LCS) problem is one of the classical and well-studied
problems in computer science. The computation of the LCS is a frequent task in DNA …
problems in computer science. The computation of the LCS is a frequent task in DNA …
Constrained longest common subsequence computing algorithms in practice
S Deorowicz, J Obstój - Computing and Informatics, 2010 - cai.sk
The problem of finding a constrained longest common subsequence (CLCS) for the
sequences A and B with respect to sequence P was introduced recently. Its goal is to find a …
sequences A and B with respect to sequence P was introduced recently. Its goal is to find a …
[PDF][PDF] 一种带匹配路径约束的最长公共子序列长度算法
王前东 - 电子与信息学报, 2017 - edit.jeit.ac.cn
在带约束的最长公共子序列问题中提出一种特殊的新问题: 假设有两序列Q 和C, Q
中指定的匹配位置序列I, 计算两序列Q 和C 的最长公共子序列, 且这个最长公共子序列的匹配 …
中指定的匹配位置序列I, 计算两序列Q 和C 的最长公共子序列, 且这个最长公共子序列的匹配 …