Approximate Boyer–Moore String Matching

DOI10.1137/0222018MaRDI QIDQ4032935zbMATH OpenOpenAlexFDO

Authors Jorma Tarhio, Esko Ukkonen

Publication date 17 May 1993

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0222018

zbMATH Keywords

edit distancestring matching\(k\) differences\(k\) mismatchesBoyer- Moore algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Recommendations

• Boyer-Moore approach to approximate string matching
• Approximate Boyer-Moore string matching for small alphabets
• scientific article; zbMATH DE number 4119620
• Fast and practical approximate string matching
• Fast string matching with mismatches

Cited in

(20)

• On-line approximate string matching with bounded errors
• On using q-gram locations in approximate string matching
• An improved algorithm for computing the edit distance of run-length coded strings
• A subquadratic algorithm for approximate limited expression matching
• Approximate string matching with reduced alphabet
• String searching with mismatches using AVX2 and AVX-512 instructions
• The Boyer-Moore-Horspool heuristic with Markovian input
• Edit distance for a run-length-encoded string and an uncompressed string
• Two glass balls and a tower
• Fast parameterized matching with \(q\)-grams
• On-Line Approximate String Searching Algorithms: Survey and Experimental Results
• Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm
• Approximate Boyer-Moore string matching for small alphabets
• An approximate string-matching algorithm
• IDPM: an improved degenerate pattern matching algorithm for biological sequences
• New and faster filters for multiple approximate string matching
• A new filtration method and a hybrid strategy for approximate string matching
• On the string matching with \(k\) mismatches
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Boyer-Moore approach to approximate string matching

This page was built for publication: Approximate Boyer–Moore String Matching

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