A sublinear algorithm for approximate keyword searching
From MaRDI portal
Publication:1336965
DOI10.1007/BF01185432zbMath0941.68560MaRDI QIDQ1336965
Publication date: 26 February 1996
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01185432
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