Space-efficient STR-IC-LCS computation

DOI10.1007/978-3-031-23101-8_25zbMath1529.68332arXiv2210.07979OpenAlexW4313429639MaRDI QIDQ6169544

Hideo Bannai, Yuto Nakashima, Yuuki Yonemoto, Shunsuke Inenaga

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)

Cites Work

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

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