A faster algorithm computing string edit distances

1980/02/01 by William Joseph Masek, William J. Masek, Michael S. Paterson · 7 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Alphabet #Artificial intelligence #Combinatorics #Computer science #Discrete mathematics #Edit distance #Longest common subsequence problem #Mathematics #Natural Language Processing Techniques #Pattern matching #Programming language #Sequence (biology) #String (physics) #String searching algorithm #Subsequence #Symbol (formal) #semigroups and automata theory

paper · doi:10.1016/0022-0000(80)90002-1

crossref issued 1980/02/01 · crossref published 1980/02/01 · crossref published-print 1980/02/01 · openalex publication_date 1980/02/01 · crossref created 2003/12/04 · crossref deposited 2019/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23 · crossref indexed 2026/08/04

Citations

• The String-to-String Correction Problem
• A linear space algorithm for computing maximal common subsequences

Cited by

• A guided tour to approximate string matching
• Consequences of Faster Alignment of Sequences
• Algorithms for Normalized Multiple Sequence Alignments
• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
• Sampling rate-corrected analysis of irregularly sampled time series
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Longest common subsequence [wikipedia]