Faster space-efficient STR-IC-LCS computation

DOI10.1016/J.TCS.2024.114607zbMATH Open1540.68334MaRDI QIDQ6549673FDOQ6549673

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

Publication date: 4 June 2024

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

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

zbMATH Keywords

dynamic programmingstring algorithmsconstrained longest common subsequence

Mathematics Subject Classification ID

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
• Space-efficient STR-IC-LCS computation
• Faster STR-IC-LCS computation via RLE
• 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)