Abstract

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 longest subsequence C of A and B such that P is a subsequence of C. There are several algorithms solving the CLCS problem, but there is no real experimental comparison of them. The paper has two aims. Firstly, we propose an improvement to the algorithms by Chin et al. and Deorowicz based on an entry-exit points technique by He and Arslan. Secondly, we compare experimentally the existing algorithms for solving the CLCS problem.

Keywords

MSC

68W05

Cite this article

@article{cai-1971,
  author  = {Sebastian Deorowicz and Joanna Obstój},
  title   = {Constrained Longest Common Subsequence Computing Algorithms in Practice},
  journal = {Computing and Informatics},
  volume  = {29},
  number  = {3},
  pages   = {427--445},
  year    = {2010},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2010/3/constrained-longest-common-subsequence-computing-algorithms-in-practice/}
}
Download .bib