Approximate Boyer-Moore string matching for small alphabets

DOI10.1007/s00453-009-9286-3zbMath1198.68122OpenAlexW1964804652MaRDI QIDQ1957645

Leena Salmela, Jorma Tarhio, Petri Kalsi

Publication date: 27 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9286-3

zbMATH Keywords

Hamming distanceEdit distanceApproximate string matchingBiological sequencesComplexity of algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Formal languages and automata (68Q45)

Related Items (2)

Average complexity of backward \(q\)-gram string matching algorithms ⋮ A randomized numerical aligner (rNA)

Uses Software

• EMBOSS

Cites Work

• Unnamed Item
• A faster algorithm computing string edit distances
• Fast string matching with mismatches
• Fast and practical approximate string matching
• A subquadratic algorithm for approximate limited expression matching
• A fast string searching algorithm
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Approximate Boyer–Moore String Matching
• Fast and flexible string matching by combining bit-parallelism and suffix automata
• Average-optimal single and multiple approximate string matching
• Combinatorial Pattern Matching

This page was built for publication: Approximate Boyer-Moore string matching for small alphabets