A sublinear algorithm for approximate keyword searching

DOI10.1007/BF01185432zbMath0941.68560MaRDI QIDQ1336965

Eugene W. Myers

Publication date: 26 February 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01185432

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C39: Dynamic programming

92D20: Protein sequences, DNA sequences

68P20: Information storage and retrieval of data

Related Items

New and faster filters for multiple approximate string matching, What’s Behind Blast, Multiple approximate string matching, A metric index for approximate string matching, Text indexing with errors, A new method for approximate indexing and dictionary lookup with one error, Approximate string matching with compressed indexes, Multiple filtration and approximate pattern matching, A subquadratic algorithm for approximate limited expression matching, Efficient generation of super condensed neighborhoods, Indexing text with approximate \(q\)-grams, Fast Approximate Search in Large Dictionaries

Cites Work

• An \(O(ND)\) difference algorithm and its variations
• A subquadratic algorithm for approximate limited expression matching
• A fast string searching algorithm
• An Improved Algorithm For Approximate String Matching
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• The theory and computation of evolutionary distances: Pattern recognition
• Fast Pattern Matching in Strings