Efficient merged longest common subsequence algorithms for similar sequences

DOI10.1016/j.tcs.2017.10.027zbMath1382.68350OpenAlexW2767793031MaRDI QIDQ1686075

Kuo-Tsung Tseng, Chang-Biau Yang, Shou-Fu Lo, De-Sheng Chan

Publication date: 20 December 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.10.027

zbMATH Keywords

longest common subsequence (LCS)sequence similaritymerged longest common subsequence (MLCS)

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

An efficient algorithm for the longest common palindromic subsequence problem ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem

Uses Software

• TED
• RTED

Cites Work

• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Dynamic programming algorithms for the mosaic longest common subsequence problem
• On a cyclic string-to-string correction problem
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• An \(O(ND)\) difference algorithm and its variations
• A linear space algorithm for the LCS problem
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Fast linear-space computations of longest common subsequences
• Simple and fast linear space computation of longest common subsequences
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• Edit distance for a run-length-encoded string and an uncompressed string
• Efficient algorithms for finding interleaving relationship between sequences
• Algorithms for approximate string matching
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• The String-to-String Correction Problem
• BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM
• Combinatorial Pattern Matching