A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

DOI10.1016/J.IPL.2008.07.005MaRDI QIDQ975491zbMATH OpenOpenAlexFDO

Authors Hsing-Yen Ann, Chang-Biau Yang, Chiou-Ting Tseng, Chiou-Yi Hor

Publication date 9 June 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.07.005

zbMATH Keywords

design of algorithmsedit distancelongest common subsequencerun-length encoding

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Computing the longest common subsequence of two run-length encoded strings
• A fast longest common subsequence algorithm for similar strings
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• A new efficient algorithm for computing the longest common subsequence
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• A fast algorithm of constrained longest common subsequence
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites work

• A fast algorithm for computing longest common subsequences
• A unifying look at data structures
• Algorithms for the Longest Common Subsequence Problem
• An improved algorithm for computing the edit distance of run-length coded strings
• Edit distance for a run-length-encoded string and an uncompressed string
• Edit distance of run-length encoded strings.
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Matching for run-length encoded strings
• Simple and fast linear space computation of longest common subsequences
• The String-to-String Correction Problem

Cited in

(20)

• Matching for run-length encoded strings
• Efficient merged longest common subsequence algorithms for similar sequences
• Edit distance of run-length encoded strings.
• The generalized definitions of the two-dimensional largest common substructure problems
• Finding the gapped longest common subsequence by incremental suffix maximum queries
• A diagonal-based algorithm for the longest common increasing subsequence problem
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Dynamic RLE-compressed edit distance tables under general weighted cost functions
• Sequence Alignment Algorithms for Run-Length-Encoded Strings
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• On computing average common substring over run length encoded sequences
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Computing the longest common subsequence of two run-length encoded strings
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• RLE edit distance in near optimal time
• Faster STR-IC-LCS computation via RLE
• An algorithm and applications to sequence alignment with weighted constraints
• The generalized constrained longest common subsequence in the run-length encoded format

This page was built for publication: A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

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