arXiv Open Access 2011

Quadratic-time Algorithm for the String Constrained LCS Problem

Sebastian Deorowicz

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (1)

Sebastian Deorowicz

Format Sitasi

APA MLA BibTeX

Deorowicz, S. (2011). Quadratic-time Algorithm for the String Constrained LCS Problem. https://arxiv.org/abs/1106.6342

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2011
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓