Quadratic-time algorithm for a string constrained LCS problem |
| |
Authors: | Sebastian Deorowicz |
| |
Affiliation: | Silesian University of Technology, Institute of Informatics, Akademicka 16, Gliwice, Poland |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|