Approximate String Matching: A Simpler Faster Algorithm

DOI10.1137/S0097539700370527zbMath1008.68165OpenAlexW2091929432MaRDI QIDQ3149893

Ramesh Hariharan, Richard John Cole

Publication date: 29 September 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700370527

zbMATH Keywords

algorithmsstring matchingedit distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items (14)

Longest common extensions in trees ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ Optimal spaced seeds for faster approximate string matching ⋮ Longest Common Extensions in Trees ⋮ Longest Common Extensions in Sublinear Space ⋮ Elastic-degenerate string matching with 1 error ⋮ Towards optimal packed string matching ⋮ Time-space trade-offs for longest common extensions ⋮ A practical semi-external memory method for approximate pattern matching ⋮ Faster approximate string matching for short patterns ⋮ String indexing for patterns with wildcards ⋮ ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Approximate pattern matching in LZ77-compressed texts

This page was built for publication: Approximate String Matching: A Simpler Faster Algorithm