Data structures and algorithms for approximate string matching

DOI10.1016/0885-064X(88)90008-8zbMath0646.68078OpenAlexW1981320868MaRDI QIDQ1104103

Raffaele Giancarlo, Zvi Galil

Publication date: 1988

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(88)90008-8

zbMATH Keywords

data structuresapproximate string matchingedit distance

Mathematics Subject Classification ID

Searching and sorting (68P10) Algorithms in computer science (68W99)

Related Items (31)

Sublinear approximate string matching and biological applications ⋮ From Nerode's congruence to suffix automata with mismatches ⋮ Boyer-Moore approach to approximate string matching ⋮ Edit distance for a run-length-encoded string and an uncompressed string ⋮ Fast approximate matching of words against a dictionary ⋮ On-line construction of suffix trees ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Multiple filtration and approximate pattern matching ⋮ EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗ ⋮ A dynamic edit distance table ⋮ Analysis of two-dimensional approximate pattern matching algorithms ⋮ A linear-time algorithm for the 1-mismatch problem ⋮ Block edit models for approximate string matching ⋮ On the Suffix Automaton with Mismatches ⋮ String matching with weighted errors ⋮ Extending alignments with \(k\)-mismatches and \(\ell\)-gaps ⋮ An efficient algorithm for some tree matching problems ⋮ A note on the subtree isomorphism for ordered trees and related problems ⋮ Full-Text Indexes for High-Throughput Sequencing ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ Approximate string-matching with \(q\)-grams and maximal matches ⋮ On similarity of polynomial configurations ⋮ Approximate string matching with suffix automata ⋮ Faster approximate string matching for short patterns ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ Simple and efficient string matching with k mismatches ⋮ Fast parallel and serial multidimensional approximate array matching ⋮ Optimal data compression algorithm ⋮ Universal Data Compression Algorithm Based on Approximate String Matching ⋮ Efficient algorithms for approximate string matching with swaps ⋮ A model and a fast algorithm for multiple errors spelling correction

Cites Work

• Efficient string matching with k mismatches
• The longest common subsequence problem revisited
• Parallel string matching with k mismatches
• A faster algorithm computing string edit distances
• A fast string searching algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• An Efficient General-Purpose Parallel Computer
• Finding approximate patterns in strings
• Generalized String Matching
• Parallel Prefix Computation
• A linear space algorithm for computing maximal common subsequences
• A Space-Economical Suffix Tree Construction Algorithm
• A fast algorithm for computing longest common subsequences
• The String-to-String Correction Problem
• Parallelism in random access machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Data structures and algorithms for approximate string matching