文章基本信息

标题：Faster STR-IC-LCS Computation via RLE
本地全文：下载
作者：Keita Kuboi ; Yuta Fujishige ; Shunsuke Inenaga 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：78
页码：20:1-20:12
DOI：10.4230/LIPIcs.CPM.2017.20
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：longest common subsequence; STR-IC-LCS; run-length encoding