Average-optimal single and multiple approximate string matching

DOI10.1145/1005813.1041513zbMath1085.68735OpenAlexW1964638897MaRDI QIDQ5463450

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

Algorithmsoptimalitybiological sequencesapproximate string matchingmultiple string matching

Mathematics Subject Classification ID

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

Related Items

Rotation and lighting invariant template matching ⋮ Approximate string matching with compressed indexes ⋮ Bit-Parallel Approximate Matching of Circular Strings with k Mismatches ⋮ A new filtration method and a hybrid strategy for approximate string matching ⋮ Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance ⋮ Average complexity of backward \(q\)-gram string matching algorithms ⋮ Approximate Boyer-Moore string matching for small alphabets ⋮ On-line approximate string matching with bounded errors ⋮ Circular pattern matching with \(k\) mismatches ⋮ Quasi-Linear-Time Algorithm for Longest Common Circular Factor ⋮ Average-optimal string matching ⋮ Sequential and indexed two-dimensional combinatorial template matching allowing rotations

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