Faster algorithms for string matching with k mismatches
From MaRDI portal
Publication:4820884
DOI10.1016/S0196-6774(03)00097-XzbMath1103.68129OpenAlexW3137072739MaRDI QIDQ4820884
Ely Porat, Amihood Amir, Moshe Lewenstein
Publication date: 1 October 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00097-x
Hamming distanceDesign and analysis of algorithmsCombinatorial algorithms on wordsApproximate string matching
Related Items (53)
On-line string matching in highly similar DNA sequences ⋮ Longest common extensions in trees ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ \(L_{1}\) pattern matching lower bound ⋮ Pattern matching with don't cares and few errors ⋮ Optimal spaced seeds for faster approximate string matching ⋮ On pattern matching with \(k\) mismatches and few don't cares ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ The approximate swap and mismatch edit distance ⋮ Permuted function matching ⋮ A filtering algorithm for \(k\)-mismatch with don't cares ⋮ Longest Common Extensions in Trees ⋮ Longest Common Extensions in Sublinear Space ⋮ Longest common extension ⋮ Checking whether a word is Hamming-isometric in linear time ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Indexing a sequence for mapping reads with a single mismatch ⋮ A Black Box for Online Approximate Pattern Matching ⋮ A new efficient indexing algorithm for one-dimensional real scaled patterns ⋮ Mismatch sampling ⋮ Elastic-degenerate string matching with 1 error ⋮ The indexing for one-dimensional proportionally-scaled strings ⋮ Unnamed Item ⋮ Time-space trade-offs for longest common extensions ⋮ String matching with up to \(k\) swaps and mismatches ⋮ Approximate pattern matching with \(k\)-mismatches in packed text ⋮ 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. ⋮ On string matching with mismatches ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ On the string matching with \(k\) mismatches ⋮ A randomized numerical aligner (rNA) ⋮ String indexing for patterns with wildcards ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ Matching with don't-cares and a small number of mismatches ⋮ A black box for online approximate pattern matching ⋮ Unnamed Item ⋮ Hardness of comparing two run-length encoded strings ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ \(k\)-difference matching in amortized linear time for all the words in a text ⋮ Circular pattern matching with \(k\) mismatches ⋮ Longest common substring made fully dynamic ⋮ Approximating Approximate Pattern Matching ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Matchstick puzzles on a grid ⋮ Unnamed Item ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Recent advances in text-to-pattern distance algorithms ⋮ Approximate hashing for bioinformatics ⋮ Streaming dictionary matching with mismatches
This page was built for publication: Faster algorithms for string matching with k mismatches
