LCS\(k\): a refined similarity measure

DOI10.1016/j.tcs.2015.11.026zbMath1344.68309OpenAlexW2189173184MaRDI QIDQ294924

S. Maimoni, D. Noifeld, B. Riva Shalom, Avivit Levy, Gary Benson

Publication date: 16 June 2016

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

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

zbMATH Keywords

dynamic programmingedit distancelongest common subsequencesimilarity of strings

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Exploiting pseudo-locality of interchange distance, Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings, On the positive semi-definite property of similarity matrices, Tight conditional lower bounds for longest common increasing subsequence, Unnamed Item, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites Work

• Unnamed Item
• On the generalized constrained longest common subsequence problems
• LCS approximation via embedding into locally non-repetitive strings
• The constrained longest common subsequence problem
• Matching for run-length encoded strings
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• A bit-string longest-common-subsequence algorithm
• Generalized LCS
• On the Common Substring Alignment Problem
• Sparse LCS Common Substring Alignment
• A linear space algorithm for computing maximal common subsequences
• The String-to-String Correction Problem
• A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm
• Combinatorial Pattern Matching
• Weighted LCS