Linear-space S-table algorithms for the longest common subsequence problem

DOI10.1016/J.TCS.2023.113944MaRDI QIDQ6104353zbMATH OpenFDO

Authors Bi-Shiang Lin, Kuo-Si Huang, Chang-Biau Yang

Publication date 15 June 2023

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

Full work available at URL https://doi.org/10.1016/J.TCS.2023.113944

zbMATH Keywords

linear spacelongest common subsequenceincremental updateconcatenation and mergingS-table

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Fast linear-space computations of longest common subsequences
• The longest common subsequence problem revisited
• Two algorithms for LCS consecutive suffix alignment
• A new practical linear space algorithm for the longest common subsequence problem
• Combinatorial Pattern Matching

Cites work

• scientific article; zbMATH DE number 5158495 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A bit-string longest-common-subsequence algorithm
• A fast algorithm for computing longest common subsequences
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• A linear space algorithm for computing maximal common subsequences
• A linear-time algorithm for a special case of disjoint set union
• A simple algorithm for the constrained sequence problems
• Algorithms for the Longest Common Subsequence Problem
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An algorithm and applications to sequence alignment with weighted constraints
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient algorithms for finding interleaving relationship between sequences
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Efficient merged longest common subsequence algorithms for similar sequences
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Geometric applications of a matrix-searching algorithm
• Incremental String Comparison
• Internet packet filter management and rectangle geometry
• Multivariate fine-grained complexity of longest common subsequence
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• On a cyclic string-to-string correction problem
• On the common substring alignment problem
• Sparse LCS common substring alignment
• The String-to-String Correction Problem
• The constrained longest common subsequence problem
• Two algorithms for LCS consecutive suffix alignment

Cited in

(2)

• Efficient algorithms for three variants of the LPF table
• String Processing and Information Retrieval

This page was built for publication: Linear-space S-table algorithms for the longest common subsequence problem

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