On string matching with mismatches

DOI10.3390/A8020248MaRDI QIDQ1736652zbMATH OpenOpenAlexFDO

Authors Marius Nicolae, Sanguthevar Rajasekaran

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1305413 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2119723 (Why is no real title available?)
• A Black Box for Online Approximate Pattern Matching
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A filtering algorithm for \(k\)-mismatch with don't cares
• A randomized algorithm for approximate string matching
• An elegant algorithm for the construction of suffix arrays
• Efficient string matching
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast Pattern Matching in Strings
• Fast algorithms for approximately counting mismatches
• Faster algorithms for string matching with k mismatches
• From coding theory to efficient pattern matching
• Generalized String Matching
• Improved Sketching of Hamming Distance with Error Correcting
• Mismatch sampling
• Simple deterministic wildcard matching
• k-Mismatch with Don’t Cares

Cited in

(17)

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

Describes a project that uses

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)