Quadratic-time algorithm for a string constrained LCS problem

Sebastian Deorowicz

doi:10.1016/j.ipl.2012.02.007

Quadratic-time algorithm for a string constrained LCS problem

Sebastian Deorowicz

Department of Algorithmics and Software (RAU/RAU5)

Research output: Contribution to journal › Article › peer-review

29 Citations (Scopus)

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.

Original language	English
Pages (from-to)	423-426
Number of pages	4
Journal	Information Processing Letters
Volume	112
Issue number	11
DOIs	https://doi.org/10.1016/j.ipl.2012.02.007
Publication status	Published - 15 Jun 2012

Keywords

Algorithms
Constrained longest common subsequence
Longest common subsequence
Sequence similarity

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2012.02.007

Cite this

@article{d6b8c2975d394ff1bc8a99547e17fb23,

title = "Quadratic-time algorithm for a string constrained LCS problem",

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 = "Algorithms, Constrained longest common subsequence, Longest common subsequence, Sequence similarity",

author = "Sebastian Deorowicz",

year = "2012",

month = jun,

day = "15",

doi = "10.1016/j.ipl.2012.02.007",

language = "English",

volume = "112",

pages = "423--426",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - Quadratic-time algorithm for a string constrained LCS problem

AU - Deorowicz, Sebastian

PY - 2012/6/15

Y1 - 2012/6/15

N2 - 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.

AB - 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.

KW - Algorithms

KW - Constrained longest common subsequence

KW - Longest common subsequence

KW - Sequence similarity

UR - https://www.scopus.com/pages/publications/84858714656

U2 - 10.1016/j.ipl.2012.02.007

DO - 10.1016/j.ipl.2012.02.007

M3 - Article

AN - SCOPUS:84858714656

SN - 0020-0190

VL - 112

SP - 423

EP - 426

JO - Information Processing Letters

JF - Information Processing Letters

IS - 11

ER -

Quadratic-time algorithm for a string constrained LCS problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this