A fast longest common subsequence algorithm for similar strings

DOI10.1007/978-3-642-13089-2_7MaRDI QIDQ3564851zbMATH OpenOpenAlexFDO

Authors Abdullah N. Arslan

Publication date 26 May 2010

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13089-2_7

zbMATH Keywords

algorithmdynamic programmingedit distancelongest common extensionlongest common subsequencelowest common ancestorstringsuffix arraysuffix tree

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• The longest common subsequence problem revisited
• An \(O(ND)\) difference algorithm and its variations
• Publication:4862293
• Fast linear-space computations of longest common subsequences
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

Cited in

(24)

• Semi-local longest common subsequences in subquadratic time
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• An \(O(ND)\) difference algorithm and its variations
• Matching for run-length encoded strings
• Efficient merged longest common subsequence algorithms for similar sequences
• Comparison of strings belonging to the same family
• A data structure for substring-substring LCS length queries
• Dynamic and internal longest common substring
• Finding the gapped longest common subsequence by incremental suffix maximum queries
• Two algorithms for LCS consecutive suffix alignment
• An \(O(n\log n)\) algorithm for finding dissimilar strings
• LCSk: a refined similarity measure
• A new algorithm for the characteristic string problem under loose similarity criteria
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Incremental String Comparison
• Longest common substring made fully dynamic
• Longest common factor after one edit operation
• Massively parallel approximation algorithms for edit distance and longest common subsequence
• Combinatorial Pattern Matching
• LCS approximation via embedding into locally non-repetitive strings
• An O(NP) sequence comparison algorithm
• Semi-local string comparison: algorithmic techniques and applications
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings

This page was built for publication: A fast longest common subsequence algorithm for similar strings

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