An O(NP) sequence comparison algorithm

DOI10.1016/0020-0190(90)90035-VzbMath0698.68055MaRDI QIDQ912628

Gene Myers, Webb Miller, Udi Manber, Sun Wu

Publication date: 1990

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

zbMATH Keywords

sequence comparison; longest commong subsequence; shortest edit script

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

Mining Bit-Parallel LCS-length Algorithms, A learning algorithm for the longest common subsequence problem, Calculating distances for dissimilar strings: the shortest path formulation revisited, Simple and fast linear space computation of longest common subsequences, Fast Algorithms for Local Similarity Queries in Two Sequences, Unnamed Item, APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest paths in Euclidean graphs
• An \(O(ND)\) difference algorithm and its variations
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Algorithms for approximate string matching
• A linear space algorithm for computing maximal common subsequences
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem