An Improved Algorithm For Approximate String Matching

DOI10.1137/0219067zbMath0711.68048OpenAlexW1970707909MaRDI QIDQ3495647

Kun Soo Park, Zvi Galil

Publication date: 1990

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

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

zbMATH Keywords

approximate string matchingedit distanceedit sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Computing methodologies for text processing; mathematical typography (68U15)

Related Items (34)

Algorithms For Computing Approximate Repetitions In Musical Sequences ⋮ Sublinear approximate string matching and biological applications ⋮ A sublinear algorithm for approximate keyword searching ⋮ Matching regular expressions on uncertain data ⋮ New and faster filters for multiple approximate string matching ⋮ Average complexity of exact and approximate multiple string matching ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ Fast approximate matching of words against a dictionary ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Algorithms for approximate graph matching ⋮ Multiple filtration and approximate pattern matching ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ A dynamic edit distance table ⋮ Analysis of two-dimensional approximate pattern matching algorithms ⋮ Multiple approximate string matching ⋮ Block edit models for approximate string matching ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ Isometric words based on swap and mismatch distance ⋮ Overlap matching. ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS ⋮ A fast algorithm for string matching with mismatches ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ An artificial neural network based approach for online string matching/filtering of large databases ⋮ Approximate string matching with suffix automata ⋮ Faster approximate string matching for short patterns ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ FINDING ALL APPROXIMATE GAPPED PALINDROMES ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation ⋮ Approximate string matching on Ziv--Lempel compressed text ⋮ Efficient algorithms for approximate string matching with swaps ⋮ On minimizing pattern splitting in multi-track string matching ⋮ Fast and practical approximate string matching ⋮ Approximate swapped matching.

This page was built for publication: An Improved Algorithm For Approximate String Matching