LCS approximation via embedding into locally non-repetitive strings
From MaRDI portal
Publication:716327
DOI10.1016/j.ic.2010.12.006zbMath1215.68281MaRDI QIDQ716327
Ilan Newman, Gad M. Landau, Avivit Levy
Publication date: 28 April 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.12.006
Related Items
LCS\(k\): a refined similarity measure, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse LCS common substring alignment
- The longest common subsequence problem revisited
- Fast string matching with k differences
- A faster algorithm computing string edit distances
- On the Common Substring Alignment Problem
- Approximate String Matching with Address Bit Errors
- Oblivious string embeddings and edit distance approximations
- Efficient randomized pattern-matching algorithms
- Bounds on the Complexity of the Longest Common Subsequence Problem
- A fast algorithm for computing longest common subsequences
- Algorithms for the Longest Common Subsequence Problem
- Algorithms on Strings, Trees and Sequences
- The String-to-String Correction Problem
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
- Approximating edit distance in near-linear time
- Matching Sequences under Deletion/Insertion Constraints
- Low distortion embeddings for edit distance