Data structures and algorithms for approximate string matching

DOI10.1016/0885-064X(88)90008-8MaRDI QIDQ1104103zbMATH OpenOpenAlexFDO

Authors R. 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 structuresedit distanceapproximate string matching

Mathematics Subject Classification ID

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

Recommendations

• Boyer-Moore approach to approximate string matching
• Improved approximate string matching using compressed suffix data structures
• Algorithms and Computation
• Fast and practical approximate string matching
• scientific article; zbMATH DE number 1303588

Cites work

• scientific article; zbMATH DE number 3881896 (Why is no real title available?)
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 3845091 (Why is no real title available?)
• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 3917745 (Why is no real title available?)
• scientific article; zbMATH DE number 3982538 (Why is no real title available?)
• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 4064469 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 4126691 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A fast algorithm for computing longest common subsequences
• A fast string searching algorithm
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• An Efficient General-Purpose Parallel Computer
• Efficient string matching with k mismatches
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding approximate patterns in strings
• Generalized String Matching
• Parallel Prefix Computation
• Parallel string matching with k mismatches
• Parallelism in random access machines
• The String-to-String Correction Problem
• The longest common subsequence problem revisited

Cited in

(42)

• Construction of Fundamental Data Structures for Strings
• Full-text indexes for high-throughput sequencing
• Approximate word sequence matching on an inverted file index
• Extending alignments with k-mismatches and -gaps
• Simple and efficient string matching with k mismatches
• On similarity of polynomial configurations
• A linear-time algorithm for the 1-mismatch problem
• On the Suffix Automaton with Mismatches
• Faster approximate string matching for short patterns
• Efficient algorithms for approximate string matching with swaps
• Approximate string processing
• Approximate string-matching with q-grams and maximal matches
• Sublinear approximate string matching and biological applications
• scientific article; zbMATH DE number 1982178 (Why is no real title available?)
• Approximate string matching with suffix automata
• scientific article; zbMATH DE number 1792103 (Why is no real title available?)
• Multiple filtration and approximate pattern matching
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• An efficient algorithm for some tree matching problems
• From Nerode's congruence to suffix automata with mismatches
• EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗
• An improved algorithm for computing the edit distance of run-length coded strings
• A programmable array processor architecture for flexible approximate string matching algorithms
• scientific article; zbMATH DE number 139916 (Why is no real title available?)
• Fast approximate matching of words against a dictionary
• Optimal data compression algorithm
• Analysis of two-dimensional approximate pattern matching algorithms
• Efficient techniques for approximate record matching modulo permutations
• Edit distance for a run-length-encoded string and an uncompressed string
• Fast parallel and serial multidimensional approximate array matching
• Universal Data Compression Algorithm Based on Approximate String Matching
• Block edit models for approximate string matching
• On-Line Approximate String Searching Algorithms: Survey and Experimental Results
• On-line construction of suffix trees
• String matching with weighted errors
• Alignments and approximate string matching
• EFFICIENT AUTOMATA CONSTRUCTIONS AND APPROXIMATE AUTOMATA
• A note on the subtree isomorphism for ordered trees and related problems
• scientific article; zbMATH DE number 872102 (Why is no real title available?)
• A dynamic edit distance table
• A model and a fast algorithm for multiple errors spelling correction
• Boyer-Moore approach to approximate string matching

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

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