A lower-variance randomized algorithm for approximate string matching

DOI10.1016/j.ipl.2013.06.005zbMath1284.68646OpenAlexW2041023432MaRDI QIDQ2444913

Elena Grigorescu, Mikhail J. Atallah, Yi Wu

Publication date: 11 April 2014

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.06.005

zbMATH Keywords

convolutionFFTapproximate string matchingrandomized algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items

An acceleration of FFT-based algorithms for the match-count problem ⋮ On approximate pattern matching with thresholds

Cites Work

• Unnamed Item
• Unnamed Item
• Combinatorial pattern matching. 3rd annual symposium, Tucson, AZ, USA, April 29 -- May 1, 1992. Proceedings
• Fast algorithms for approximately counting mismatches
• Fast and practical approximate string matching
• Generalized String Matching
• FFT-based algorithms for the string matching with mismatches problem
• A randomized algorithm for approximate string matching