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 comparisonlongest commong subsequenceshortest edit script

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item