Faster space-efficient STR-IC-LCS computation

DOI10.1016/J.TCS.2024.114607MaRDI QIDQ6549673zbMATH OpenFDO

Authors Yuki Yonemoto, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

Publication date 4 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingstring algorithmsconstrained longest common subsequence

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• 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
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints

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
• Space-efficient STR-IC-LCS computation
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• The fine-grained complexity of episode matching

Cited in

(1)

• Space-efficient STR-IC-LCS computation

This page was built for publication: Faster 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 Q6549673)