On pattern matching with k mismatches and few don't cares

DOI10.1016/J.IPL.2016.10.003MaRDI QIDQ344551zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marius Nicolae, Sanguthevar Rajasekaran

Publication date 23 November 2016

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

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

zbMATH Keywords

\(k\) mismatches with don't cares in the pattern\(k\) mismatches with wild cardsalgorithmspattern matching with \(k\) mismatches and don't cares

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: We consider the problem of pattern matching with $k$ mismatches, where there can be don't care or wild card characters in the pattern. Specifically, given a pattern $P$ of length $m$ and a text $T$ of length $n$, we want to find all occurrences of $P$ in $T$ that have no more than $k$ mismatches. The pattern can have don't care characters, which match any character. Without don't cares, the best known algorithm for pattern matching with $k$ mismatches has a runtime of $O(nsqrtklogk)$. With don't cares in the pattern, the best deterministic algorithm has a runtime of $O(nkpolylogm)$. Therefore, there is an important gap between the versions with and without don't cares. In this paper we give an algorithm whose runtime increases with the number of don't cares. We define an {em island} to be a maximal length substring of $P$ that does not contain don't cares. Let $q$ be the number of islands in $P$. We present an algorithm that runs in $O(nsqrtklogm+nminsqrt[3]qklo{g}^{2}m,sqrtqlogm)$ time. If the number of islands $q$ is $O(k)$ this runtime becomes $O(nsqrtklogm)$, which essentially matches the best known runtime for pattern matching with $k$ mismatches without don't cares. If the number of islands $q$ is $O(k^2)$, this algorithm is asymptotically faster than the previous best algorithm for pattern matching with $k$ mismatches with don't cares in the pattern.

Recommendations

• On the string matching with \(k\) mismatches
• Order-preserving pattern matching with \(k\) mismatches
• Order-preserving pattern matching with \(k\) mismatches
• Circular pattern matching with k mismatches
• Circular pattern matching with \(k\) mismatches
• Approximate pattern matching with \(k\)-mismatches in packed text
• A filtering algorithm for k-mismatch with don't cares
• The \(k\)-mismatch problem revisited
• Pattern matching with non overlapping reversals -- approximation and on-line algorithms

Cites work

• A Black Box for Online Approximate Pattern Matching
• Efficient string-matching allowing for non-overlapping inversions
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast convolutions and their applications in approximate string matching
• Fast Pattern Matching in Strings
• Faster algorithms for string matching with k mismatches
• From coding theory to efficient pattern matching
• Generalized String Matching
• 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 1754502 (Why is no real title available?)
• Improved Sketching of Hamming Distance with Error Correcting
• k-Mismatch with Don’t Cares
• Mismatch sampling
• On Finding Lowest Common Ancestors in Trees
• On string matching with mismatches
• Pattern matching with don't cares and few errors
• Simple deterministic wildcard matching

Cited in

(11)

• A filtering algorithm for k-mismatch with don't cares
• Checking whether a word is Hamming-isometric in linear time
• k-Abelian Pattern Matching
• k-Mismatch with Don’t Cares
• scientific article; zbMATH DE number 5717259 (Why is no real title available?)
• \(k\)-abelian pattern matching
• Functional and Logic Programming
• Longest common extensions with wildcards: trade-off and applications
• Pattern matching with mismatches and wildcards
• Pattern matching with don't cares and few errors
• Matching with don't-cares and a small number of mismatches

This page was built for publication: On pattern matching with \(k\) mismatches and few don't cares

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