Space-efficient STR-IC-LCS computation

DOI10.1007/978-3-031-23101-8_25zbMATH Open1529.68332arXiv2210.07979OpenAlexW4313429639MaRDI QIDQ6169544FDOQ6169544

Authors: Yuuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai 

Publication date: 14 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: One of the most fundamental method for comparing two given strings $A$ and $B$ is the longest common subsequence (LCS), where the task is to find (the length) of the longest common subsequence. In this paper, we address the STR-IC-LCS problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string $Z$ is said to be an STR-IC-LCS of three given strings $A$, $B$, and $P$, if $Z$ is one of the longest common subsequences of $A$ and $B$ that contains $P$ as a substring. We present a space efficient solution for the STR-IC-LCS problem. Our algorithm computes the length of an STR-IC-LCS in $O(n^2)$ time and $O((ell+1)(n-ell+1))$ space where $ell$ is the length of a longest common subsequence of $A$ and $B$ of length $n$. When $ell=O(1)$ or $n-ell=O(1)$, then our algorithm uses only linear $O(n)$ space.

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

zbMATH Keywords

dynamic programmingconstrained longest common subsequencestring algorithm

Mathematics Subject Classification ID

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

Cites Work

• The String-to-String Correction Problem
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• The constrained longest common subsequence problem
• On the generalized constrained longest common subsequence problems
• Fast and compact regular expression matching
• A simple algorithm for the constrained sequence problems
• Quadratic-time algorithm for a string constrained LCS problem
• A longest common subsequence algorithm suitable for similar text strings
• Faster STR-EC-LCS computation
• Faster STR-IC-LCS computation via RLE

Cited In (2)

• A substring-substring LCS data structure
• Faster space-efficient STR-IC-LCS computation

This page was built for publication: Space-efficient STR-IC-LCS computation

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