Average-optimal single and multiple approximate string matching

DOI10.1145/1005813.1041513MaRDI QIDQ5463450zbMATH OpenOpenAlexFDO

Authors Kimmo Fredriksson, Gonzalo Navarro

Publication date 4 August 2005

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1005813.1041513

zbMATH Keywords

optimalityAlgorithmsmultiple string matchingapproximate string matchingbiological sequences

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Average-optimal multiple approximate string matching
• Average-optimal string matching
• Average complexity of exact and approximate multiple string matching
• Combinatorial Pattern Matching
• scientific article; zbMATH DE number 3845091
• Average optimal string matching in packed strings
• Average-case optimal approximate circular string matching
• Fast and practical approximate string matching
• Algorithms for approximate string matching
• Multiple approximate string matching

Cited in

(25)

• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Multiple approximate string matching
• On-line approximate string matching with bounded errors
• Approximate circular pattern matching
• Fast and simple computations using prefix tables under Hamming and edit distance
• On Minimizing Pattern Splitting in Multi-track String Matching
• Combinatorial Pattern Matching
• Average-optimal multiple approximate string matching
• Average complexity of backward \(q\)-gram string matching algorithms
• scientific article; zbMATH DE number 5777888 (Why is no real title available?)
• Average-optimal string matching
• Fast string matching for DNA sequences
• Average complexity of exact and approximate multiple string matching
• Quasi-linear-time algorithm for a longest common circular factor
• Optimal spaced seeds for faster approximate string matching
• Average-case optimal approximate circular string matching
• Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm
• Approximate string matching with compressed indexes
• Approximate Boyer-Moore string matching for small alphabets
• Space-Efficient Approximate String Matching Allowing Inversions in Fast Average Time
• Circular pattern matching with \(k\) mismatches
• Rotation and lighting invariant template matching
• A new filtration method and a hybrid strategy for approximate string matching
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Sequential and indexed two-dimensional combinatorial template matching allowing rotations

This page was built for publication: Average-optimal single and multiple approximate string matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463450)