A dynamic edit distance table

DOI10.1016/S1570-8667(03)00082-0zbMath1118.68757MaRDI QIDQ876720

Sung-Ryul Kim, Kun Soo Park

Publication date: 26 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

string matchingedit distanceincremental/decremental edit distance

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items

Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions, Efficient all path score computations on grid graphs, Dynamic edit distance table under a general weighted cost function, On almost Monge all scores matrices, Semi-local longest common subsequences in subquadratic time, Unnamed Item, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Approximate string matching with suffix automata
• Data structures and algorithms for approximate string matching
• Fast string matching with k differences
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• Fast parallel and serial approximate string matching
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Incremental String Comparison
• The String-to-String Correction Problem
• Approximate periods of strings