Approximate Boyer–Moore String Matching

DOI10.1137/0222018zbMATH Open0770.68074OpenAlexW2004120611MaRDI QIDQ4032935FDOQ4032935

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

Recommendations

• Boyer-Moore approach to approximate string matching
• Approximate Boyer-Moore string matching for small alphabets
• Publication:4733401
• Fast and practical approximate string matching
• Fast string matching with mismatches

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)

Cited In (19)

• 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
• 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
• 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
• Fast parameterized matching with \(q\)-grams
• 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
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• On the string matching with \(k\) mismatches
• A new filtration method and a hybrid strategy for approximate string matching
• 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)