A fast and practical bit-vector algorithm for the longest common subsequence problem

DOI10.1016/S0020-0190(01)00182-XzbMath1003.68201WikidataQ61677962 ScholiaQ61677962MaRDI QIDQ1607132

Maxime Crochemore, Costas S. Iliopoulos, Yoan J. Pinzon, James F. Reid

Publication date: 25 July 2002

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

zbMATH Keywords

longest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (14)

LCS\(k\): a refined similarity measure ⋮ Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism ⋮ Algorithms in the Ultra-Wide Word Model ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Longest bordered and periodic subsequences ⋮ Unnamed Item ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Mining Bit-Parallel LCS-length Algorithms ⋮ BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM ⋮ Practical algorithms for transposition-invariant string-matching ⋮ FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm computing string edit distances
• An information-theoretic lower bound for the longest common subsequence problem
• A subquadratic algorithm for approximate limited expression matching
• A bit-string longest-common-subsequence algorithm
• Shortcuts, diversions, and maximal chains in partially ordered sets
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Approximate string matching using withinword parallelism
• The String-to-String Correction Problem

This page was built for publication: A fast and practical bit-vector algorithm for the longest common subsequence problem