Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2017.20
URN: urn:nbn:de:0030-drops-73335
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7333/
Kuboi, Keita ; Fujishige, Yuta ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki
Faster STR-IC-LCS Computation via RLE
| pdf-format: |
|
Abstract
The constrained LCS problem asks one to find a longest common subsequence of two input strings A and B with some constraints. The STR-IC-LCS problem is a variant of the constrained LCS problem, where the solution must include a given constraint string C as a substring. Given two strings A and B of respective lengths M and N, and a constraint string C of length at most min{M, N}, the best known algorithm for the STR-IC-LCS problem, proposed by Deorowicz (Inf. Process. Lett., 11:423-426, 2012), runs in O(MN) time. In this work, we present an O(mN + nM)-time solution to the STR-IC-LCS problem, where m and n denote the sizes of the run-length encodings of A and B, respectively. Since m <= M and n <= N always hold, our algorithm is always as fast as Deorowicz's algorithm, and is faster when input strings are compressible via RLE.
BibTeX - Entry
@InProceedings{kuboi_et_al:LIPIcs:2017:7333,
author = {Keita Kuboi and Yuta Fujishige and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda},
title = {{Faster STR-IC-LCS Computation via RLE}},
booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
pages = {20:1--20:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-039-2},
ISSN = {1868-8969},
year = {2017},
volume = {78},
editor = {Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7333},
URN = {urn:nbn:de:0030-drops-73335},
doi = {10.4230/LIPIcs.CPM.2017.20},
annote = {Keywords: longest common subsequence, STR-IC-LCS, run-length encoding}
}
| Keywords: | longest common subsequence, STR-IC-LCS, run-length encoding | |
| Seminar: | 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 30.06.2017 |
