FFT-based algorithms for the string matching with mismatches problem

DOI10.1016/J.JALGOR.2005.01.001MaRDI QIDQ5711729zbMATH OpenOpenAlexFDO

Authors Tor Schoenmeyr, David Yu Zhang

Publication date 8 December 2005

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

Full work available at URL https://doi.org/10.1016/j.jalgor.2005.01.001

zbMATH Keywords

FFTHamming distanceRandomized algorithmsString matching with mismatches

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1445379
• Faster algorithms for string matching with k mismatches
• An acceleration of FFT-based algorithms for the match-count problem
• Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm
• Fast string matching with mismatches
• Efficient string matching with k mismatches
• Algorithms for approximate string matching
• Fast exact string matching algorithms

Cited in

(5)

• A lower-variance randomized algorithm for approximate string matching
• An acceleration of FFT-based algorithms for the match-count problem
• Efficient and secure generalized pattern matching via Fast Fourier Transform
• scientific article; zbMATH DE number 2052914 (Why is no real title available?)
• An efficient mapping for computing the score of string matching

This page was built for publication: FFT-based algorithms for the string matching with mismatches problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5711729)