Faster algorithms for string matching with k mismatches
From MaRDI portal
Recommendations
Cited in
(90)- \(k\)-difference matching in amortized linear time for all the words in a text
- Efficient string matching with k mismatches
- Fast string matching with k differences
- Fast average-case pattern matching by multiplexing sparse tables
- Fast algorithms for approximately counting mismatches
- Fast string matching with mismatches
- Detecting false matches in string-matching algorithms
- Permuted function matching
- A filtering algorithm for k-mismatch with don't cares
- Longest common extension
- On string matching with mismatches
- Streaming pattern matching with \(d\) wildcards
- On the string matching with \(k\) mismatches
- A randomized numerical aligner (rNA)
- Fast and practical approximate string matching
- The indexing for one-dimensional proportionally-scaled strings
- String matching with up to k swaps and mismatches
- Recent advances in text-to-pattern distance algorithms
- Approximate hashing for bioinformatics
- Streaming dictionary matching with mismatches
- Streaming \(k\)-mismatch with error correcting and applications
- Matchstick puzzles on a grid
- On-line string matching in highly similar DNA sequences
- \(L_{1}\) pattern matching lower bound
- Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Modulated string searching
- Time-space trade-offs for longest common extensions
- Approximate pattern matching with \(k\)-mismatches in packed text
- Optimal spaced seeds for faster approximate string matching
- Checking whether a word is Hamming-isometric in linear time
- Time-Space Trade-Offs for Longest Common Extensions
- Longest common extensions in trees
- Longest common extensions in sublinear space
- Longest common extensions in trees
- On the relationship between histogram indexing and block-mass indexing
- Indexing a sequence for mapping reads with a single mismatch
- Two glass balls and a tower
- Finding witnesses by peeling
- On pattern matching with \(k\) mismatches and few don't cares
- Finding Witnesses by Peeling
- A Black Box for Online Approximate Pattern Matching
- EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, kΔ, α)-MATCHING
- A randomized numerical aligner (rNA)
- Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard
- Fast convolutions and their applications in approximate string matching
- A new efficient indexing algorithm for one-dimensional real scaled patterns
- Mismatch sampling
- Inverse Pattern Matching
- The \(k\)-mismatch problem revisited
- scientific article; zbMATH DE number 1445379 (Why is no real title available?)
- Towards unified approximate pattern matching for Hamming and \(L_1\) distance
- Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
- Longest common substring made fully dynamic
- Approximating Approximate Pattern Matching
- Even faster elastic-degenerate string matching via fast matrix multiplication
- A linear-time algorithm for the 1-mismatch problem
- Streaming for aibohphobes: longest palindrome with mismatches
- Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
- Random access to grammar-compressed strings and trees
- Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
- FFT-based algorithms for the string matching with mismatches problem
- Simple and efficient string matching with k mismatches
- Elastic-Degenerate String Matching via Fast Matrix Multiplication
- Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
- Circular pattern matching with \(k\) mismatches
- Circular pattern matching with k mismatches
- The approximate swap and mismatch edit distance
- scientific article; zbMATH DE number 7758348 (Why is no real title available?)
- Elastic-degenerate string matching with 1 error
- Elastic-degenerate string matching with 1 error or mismatch
- Reconstructing general matching graphs
- Approximate circular pattern matching under edit distance
- Fast convolutions for near-convex sequences
- String searching with mismatches using AVX2 and AVX-512 instructions
- Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
- A black box for online approximate pattern matching
- Longest common extensions with wildcards: trade-off and applications
- Pattern matching with mismatches and wildcards
- Compressed dictionary matching on run-length encoded strings
- Compressed dictionary matching on run-length encoded strings
- Faster approximate elastic-degenerate string matching. Part A
- Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
- Pattern matching with don't cares and few errors
- Two problems about recovering of damaged strings
- An analysis of the Karp-Rabin string matching algorithm
- Pattern matching with address errors: rearrangement distances
- Matching with don't-cares and a small number of mismatches
- Hardness of comparing two run-length encoded strings
- A faster algorithm for matching a set of patterns with variable length don't cares
This page was built for publication: Faster algorithms for string matching with k mismatches
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4820884)
