Efficient string matching with k mismatches
From MaRDI portal
Publication:1079377
DOI10.1016/0304-3975(86)90178-7zbMATH Open0597.68055OpenAlexW4212954813WikidataQ56813210 ScholiaQ56813210MaRDI QIDQ1079377FDOQ1079377
Authors: Gad M. Landau, Uzi Vishkin 
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90178-7
Recommendations
- Simple and efficient string matching with k mismatches
- scientific article; zbMATH DE number 1445379
- Faster algorithms for string matching with k mismatches
- Fast string matching with k differences
- Fast string matching with mismatches
- On the string matching with \(k\) mismatches
- String matching with up to \(k\) swaps and mismatches
- Fast and practical approximate string matching
- K-M-P string matching revisited
- Parallel string matching with k mismatches
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Cites Work
Cited In (58)
- Top-k Substring Matching for Auto-Completion
- Elastic-degenerate string matching with 1 error or mismatch
- An efficient mapping for computing the score of string matching
- Towards unified approximate pattern matching for Hamming and \(L_1\) distance
- Efficient computation of sequence mappability
- Simple and efficient string matching with k mismatches
- Recent advances in text-to-pattern distance algorithms
- Title not available (Why is that?)
- Efficient identification of \(k\)-closed strings
- Approximate pattern matching with \(k\)-mismatches in packed text
- Pattern matching with address errors: rearrangement distances
- \(k\)-approximate quasiperiodicity under Hamming and edit distance
- Streaming dictionary matching with mismatches
- Swap and mismatch edit distance
- Fast string matching with k differences
- Title not available (Why is that?)
- Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
- Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
- Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
- Multiple filtration and approximate pattern matching
- A black box for online approximate pattern matching
- Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
- String matching with up to \(k\) swaps and mismatches
- EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗
- From Nerode's congruence to suffix automata with mismatches
- A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
- A Black Box for Online Approximate Pattern Matching
- A randomized numerical aligner (rNA)
- Verifiable pattern matching on outsourced texts
- Verifiable pattern matching on outsourced texts
- Streaming pattern matching with \(d\) wildcards
- Longest common substring with approximately \(k\) mismatches
- Elastic-Degenerate String Matching via Fast Matrix Multiplication
- The approximate swap and mismatch edit distance
- Data structures and algorithms for approximate string matching
- Approximate periodicity
- Indexing a sequence for mapping reads with a single mismatch
- Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences
- \(k\)-difference matching in amortized linear time for all the words in a text
- Elastic-degenerate string matching with 1 error
- Finding approximate palindromes in strings
- Small-space LCE data structure with constant-time queries
- On-Line Approximate String Searching Algorithms: Survey and Experimental Results
- Longest common extension
- Fast and practical approximate string matching
- Maximal degenerate palindromes with gaps and mismatches
- Efficient string-matching allowing for non-overlapping inversions
- Mismatch sampling
- What's behind blast
- FFT-based algorithms for the string matching with mismatches problem
- Nested Counters in Bit-Parallel String Matching
- Circular pattern matching with \(k\) mismatches
- Pattern matching with don't cares and few errors
- A filtering algorithm for \(k\)-mismatch with don't cares
- On the string matching with \(k\) mismatches
- Parallel string matching with k mismatches
- A fast algorithm for string matching with mismatches
- Matching patterns in strings subject to multi-linear transformations
This page was built for publication: Efficient string matching with k mismatches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079377)
