Fast algorithms for approximately counting mismatches

DOI10.1016/0020-0190(93)90177-BzbMath0788.68062OpenAlexW2008249302MaRDI QIDQ1313761

Howard J. Karloff

Publication date: 9 June 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90177-b

zbMATH Keywords

string matchingpattern matchingapproximation algorithmsrandomized algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (19)

Pattern matching with don't cares and few errors ⋮ Exploiting pseudo-locality of interchange distance ⋮ The approximate swap and mismatch edit distance ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Mismatch sampling ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A lower-variance randomized algorithm for approximate string matching ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Pattern matching with address errors: rearrangement distances ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ On string matching with mismatches ⋮ On approximate pattern matching with thresholds ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ A black box for online approximate pattern matching ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ Approximating Approximate Pattern Matching ⋮ Approximate periodicity ⋮ Recent advances in text-to-pattern distance algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized String Matching
• Simple Constructions of Almost k-wise Independent Random Variables
• Addendum to “simple constructions of almost k-wise independent random variables”

This page was built for publication: Fast algorithms for approximately counting mismatches