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

Katedra Algorytmiki i Oprogramowania (RAU/RAU5)

Wyniki badań: Wkład do czasopisma › Artykuł › recenzja

29 Cytowania z bazy Scopus

Abstrakt

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.

Język oryginału	angielski
Strony (od–do)	423-426
Liczba stron	4
Czasopismo	Information Processing Letters
Tom	112
Numer wydania	11
Identyfikatory DOI	https://doi.org/10.1016/j.ipl.2012.02.007
Status publikacji	Opublikowano - 15 cze 2012

Obszary tematyczne ASJC Scopus

Informatyka teoretyczna
Przetwarzanie sygnałów
Systemy informacyjne
Zastosowania informatyki

Uzyskaj dostęp do dokumentu

10.1016/j.ipl.2012.02.007

Inne pliki i linki

Link do publikacji w Scopus

Cytuj to

@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

Abstrakt

Obszary tematyczne ASJC Scopus

Uzyskaj dostęp do dokumentu

Inne pliki i linki

Fingerprint

Cytuj to