Efficient string matching with k mismatches

DOI10.1016/0304-3975(86)90178-7zbMath0597.68055OpenAlexW4212954813WikidataQ56813210 ScholiaQ56813210MaRDI QIDQ1079377

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

zbMATH Keywords

pattern matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (50)

Swap and mismatch edit distance ⋮ Efficient computation of sequence mappability ⋮ From Nerode's congruence to suffix automata with mismatches ⋮ Pattern matching with don't cares and few errors ⋮ Parallel string matching with k mismatches ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ Data structures and algorithms for approximate string matching ⋮ Multiple filtration and approximate pattern matching ⋮ EFFICIENT PARALLEL ALGORITHMS FOR PATTERN RECOGNITION∗ ⋮ Fast string matching with k differences ⋮ Matching patterns in strings subject to multi-linear transformations ⋮ The approximate swap and mismatch edit distance ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ Covering problems for partial words and for indeterminate strings ⋮ Longest common extension ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Indexing a sequence for mapping reads with a single mismatch ⋮ A Black Box for Online Approximate Pattern Matching ⋮ Mismatch sampling ⋮ Elastic-degenerate string matching with 1 error ⋮ Unnamed Item ⋮ String matching with up to \(k\) swaps and mismatches ⋮ Pattern matching with address errors: rearrangement distances ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ A fast algorithm for string matching with mismatches ⋮ Streaming pattern matching with \(d\) wildcards ⋮ On the string matching with \(k\) mismatches ⋮ Verifiable pattern matching on outsourced texts ⋮ A randomized numerical aligner (rNA) ⋮ String indexing for patterns with wildcards ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ A black box for online approximate pattern matching ⋮ Unnamed Item ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ Nested Counters in Bit-Parallel String Matching ⋮ \(k\)-difference matching in amortized linear time for all the words in a text ⋮ Circular pattern matching with \(k\) mismatches ⋮ Verifiable Pattern Matching on Outsourced Texts ⋮ What’s Behind Blast ⋮ Small-space LCE data structure with constant-time queries ⋮ Fast and practical approximate string matching ⋮ Efficient Identification of k-Closed Strings ⋮ Approximate periodicity ⋮ Finding approximate palindromes in strings ⋮ Recent advances in text-to-pattern distance algorithms ⋮ \(k\)-approximate quasiperiodicity under Hamming and edit distance ⋮ Streaming dictionary matching with mismatches

Cites Work

• Unnamed Item
• Time-space-optimal string matching
• On the computational power of pushdown automata
• A fast string searching algorithm
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings

This page was built for publication: Efficient string matching with k mismatches