The approximate swap and mismatch edit distance

DOI10.1016/J.TCS.2010.06.004zbMath1206.68106OpenAlexW2052231302MaRDI QIDQ604463

Ely Porat, Asaf Tsur, Benny Porat, Ohad Lipsky, Yair Dombb

Publication date: 11 November 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.004

zbMATH Keywords

pattern matchingmismatchswapedit operations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Randomized algorithms (68W20)

Related Items (2)

Isometric words based on swap and mismatch distance ⋮ String matching with up to \(k\) swaps and mismatches

Cites Work

• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Overlap matching.
• Approximate swapped matching.
• Generalized String Matching
• An Extension of the String-to-String Correction Problem
• Fast parallel and serial approximate string matching
• Faster algorithms for string matching with k mismatches
• Algorithms – ESA 2004
• A randomized algorithm for approximate string matching
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The approximate swap and mismatch edit distance