On string matching with mismatches

DOI10.3390/A8020248zbMATH Open1462.68246arXiv1307.1406OpenAlexW1803321205MaRDI QIDQ1736652FDOQ1736652

Authors: Marius Nicolae, Sanguthevar Rajasekaran 

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Abstract: In this paper we consider several variants of the pattern matching problem. In particular, we investigate the following problems: 1) Pattern matching with k mismatches; 2) Approximate counting of mismatches; and 3) Pattern matching with mismatches. The distance metric used is the Hamming distance. We present some novel algorithms and techniques for solving these problems. Both deterministic and randomized algorithms are offered. Variants of these problems where there could be wild cards in either the text or the pattern or both are considered. An experimental evaluation of these algorithms is also presented. The source code is available at http://www.engr.uconn.edu/~man09004/kmis.zip.

Full work available at URL: https://arxiv.org/abs/1307.1406

Recommendations

• scientific article; zbMATH DE number 1445379
• Approximate pattern matching with \(k\)-mismatches in packed text
• Faster algorithms for string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Mismatch sampling

zbMATH Keywords

pattern matching with mismatchesapproximate counting of mismatchesk-mismatches problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Efficient string matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Fast Pattern Matching in Strings
• Fast algorithms for approximately counting mismatches
• Generalized String Matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Faster algorithms for string matching with k mismatches
• Simple deterministic wildcard matching
• A filtering algorithm for \(k\)-mismatch with don't cares
• Improved Sketching of Hamming Distance with Error Correcting
• A Black Box for Online Approximate Pattern Matching
• k-Mismatch with Don’t Cares
• Title not available (Why is that?)
• Mismatch sampling
• Exact and Approximate Pattern Matching in the Streaming Model
• An elegant algorithm for the construction of suffix arrays
• A randomized algorithm for approximate string matching

Cited In (15)

• Generalized String Matching
• Three one-way heads cannot do string matching
• Matchstick puzzles on a grid
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Pattern matching in the Hamming distance with thresholds
• Title not available (Why is that?)
• Matching a set of strings with variable length don't cares
• Finding approximate repetitions under Hamming distance.
• Fast algorithms for approximately counting mismatches
• String matching with simple devices
• Two-way string-matching
• Longest common extension
• On pattern matching with \(k\) mismatches and few don't cares
• Mismatch sampling
• String matching with lookahead

Uses Software

• FFTW

This page was built for publication: On string matching with mismatches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736652)