Faster STR-IC-LCS computation via RLE

DOI10.4230/LIPICS.CPM.2017.20MaRDI QIDQ5110885zbMATH OpenOpenAlexFDO

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

Publication date 25 May 2020

Full work available at URL https://arxiv.org/abs/1703.04954

zbMATH Keywords

longest common subsequencerun-length encodingSTR-IC-LCS

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

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 $minM,N$, the best known algorithm for the STR-IC-LCS problem, proposed by Deorowicz~({em 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 $mleqM$ and $nleqN$ always hold, our algorithm is always as fast as Deorowicz's algorithm, and is faster when input strings are compressible via RLE.

Recommendations

• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Faster STR-EC-LCS computation
• New efficient algorithms for the LCS and constrained LCS problems
• Quadratic-time algorithm for a string constrained LCS problem
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

Cited in

(8)

• Faster STR-EC-LCS computation
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Almost linear time computation of maximal repetitions in run length encoded strings
• Computing longest common square subsequences
• Space-efficient STR-IC-LCS computation
• Faster space-efficient STR-IC-LCS computation
• The generalized constrained longest common subsequence in the run-length encoded format

This page was built for publication: Faster STR-IC-LCS computation via RLE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110885)