Faster STR-IC-LCS Computation via RLE

Keita Kuboi, Yuta Fujishige, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)


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.

Original languageEnglish
Title of host publication28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017
EditorsJakub Radoszewski, Juha Karkkainen, Jakub Radoszewski, Wojciech Rytter
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770392
Publication statusPublished - Jul 1 2017
Event28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017 - Warsaw, Poland
Duration: Jul 4 2017Jul 6 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Faster STR-IC-LCS Computation via RLE'. Together they form a unique fingerprint.

Cite this