Simple and efficient string matching with k mismatches

DOI10.1016/0020-0190(89)90188-9zbMath0689.68054OpenAlexW2057097754MaRDI QIDQ582093

Roberto Grossi, Fabrizio Luccio

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90188-9

zbMATH Keywords

design of algorithmsapproximate string matchingsuffix treemismatches

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items (13)

New and faster filters for multiple approximate string matching ⋮ Boyer-Moore approach to approximate string matching ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Multiple filtration and approximate pattern matching ⋮ Efficient string-matching allowing for non-overlapping inversions ⋮ On using q-gram locations in approximate string matching ⋮ String matching with inversions and translocations in linear average time (most of the time) ⋮ Average-case linear-time similar substring searching by the \(q\)-gram distance ⋮ Text searching allowing for inversions and translocations of factors ⋮ Approximate string-matching with \(q\)-grams and maximal matches ⋮ Algorithms for finding a most similar subforest ⋮ Improved online algorithms for jumbled matching ⋮ Fast and practical approximate string matching

Cites Work

• Unnamed Item
• Unnamed Item
• Data structures and algorithms for approximate string matching
• Fast string matching with k differences
• Time-space-optimal string matching
• A fast string searching algorithm
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching

This page was built for publication: Simple and efficient string matching with k mismatches