2026-07-25T06:42:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7333 2024-03-06T10:40:08Z ddc:004 open_access

Faster STR-IC-LCS Computation via RLE Kuboi, Keita Fujishige, Yuta Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki longest common subsequence STR-IC-LCS run-length encoding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Keita Kuboi and Yuta Fujishige and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.20 urn:nbn:de:0030-drops-73335 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode