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

DOI10.1016/j.ipl.2008.07.005zbMath1191.68818OpenAlexW2111356103MaRDI QIDQ975491

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

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 algorithmsrun-length encodingedit distancelongest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (11)

Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem

Cites Work

• Unnamed Item
• Unnamed Item
• An improved algorithm for computing the edit distance of run-length coded strings
• Matching for run-length encoded strings
• Simple and fast linear space computation of longest common subsequences
• Edit distance of run-length encoded strings.
• Edit distance for a run-length-encoded string and an uncompressed string
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Fast Algorithms for Finding Nearest Common Ancestors
• A unifying look at data structures
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem

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