Data structures and algorithms for approximate string matching
From MaRDI portal
Publication:1104103
DOI10.1016/0885-064X(88)90008-8zbMath0646.68078OpenAlexW1981320868MaRDI QIDQ1104103
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
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