Approximate Boyer–Moore String Matching

DOI10.1137/0222018zbMath0770.68074OpenAlexW2004120611MaRDI QIDQ4032935

Esko Ukkonen, Jorma Tarhio

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

string matchingedit distance\(k\) differences\(k\) mismatchesBoyer- Moore algorithm

Mathematics Subject Classification ID

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

Related Items (13)

New and faster filters for multiple approximate string matching ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Bit-Parallel Approximate Matching of Circular Strings with k Mismatches ⋮ A new filtration method and a hybrid strategy for approximate string matching ⋮ On using q-gram locations in approximate string matching ⋮ Approximate Boyer-Moore string matching for small alphabets ⋮ On-line approximate string matching with bounded errors ⋮ IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ On the string matching with \(k\) mismatches ⋮ Fast parameterized matching with \(q\)-grams

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