Space-efficient STR-IC-LCS computation

DOI10.1007/978-3-031-23101-8_25MaRDI QIDQ6169544zbMATH OpenOpenAlexFDO

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)

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)

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.

Recommendations

• Faster space-efficient STR-IC-LCS computation
• Faster STR-EC-LCS computation
• Faster STR-IC-LCS computation via RLE
• New efficient algorithms for the LCS and constrained LCS problems
• Longest common subsequence in sublinear space

Cites work

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

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)