| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427735 | Information Processing Letters | 2012 | 4 Pages |
Abstract
The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.
► We investigate a string constrained LCS problem. ► We propose the first quadratic-time algorithm for the problem. ► We point out a flaw in some literature algorithm for the related problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sebastian Deorowicz,