Tags

Type your tag names separated by a space and hit enter

On pattern matching with k mismatches and few don't cares.
Inf Process Lett. 2017 Feb; 118:78-82.IP

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 [Formula: see text]. With don't cares in the pattern, the best deterministic algorithm has a runtime of O(nk polylog m). 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 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 [Formula: see text] time. If the number of islands q is O(k) this runtime becomes [Formula: see text], 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(k2), this algorithm is asymptotically faster than the previous best algorithm for pattern matching with k mismatches with don't cares in the pattern.

Authors+Show Affiliations

Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Way Unit 4155, Storrs, CT 06269, USA.Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Way Unit 4155, Storrs, CT 06269, USA.

Pub Type(s)

Journal Article

Language

eng

PubMed ID

28630523

Citation

Nicolae, Marius, and Sanguthevar Rajasekaran. "On Pattern Matching With K Mismatches and Few Don't Cares." Information Processing Letters, vol. 118, 2017, pp. 78-82.
Nicolae M, Rajasekaran S. On pattern matching with k mismatches and few don't cares. Information processing letters. 2017;118:78-82.
Nicolae, M., & Rajasekaran, S. (2017). On pattern matching with k mismatches and few don't cares. Information Processing Letters, 118, 78-82. https://doi.org/10.1016/j.ipl.2016.10.003
Nicolae M, Rajasekaran S. On Pattern Matching With K Mismatches and Few Don't Cares. Information processing letters. 2017;118:78-82. PubMed PMID: 28630523.
* Article titles in AMA citation format should be in sentence-case
TY - JOUR T1 - On pattern matching with k mismatches and few don't cares. AU - Nicolae,Marius, AU - Rajasekaran,Sanguthevar, Y1 - 2016/10/27/ PY - 2017/6/21/entrez PY - 2017/6/21/pubmed PY - 2017/6/21/medline KW - k mismatches with don’t cares in the pattern KW - k mismatches with wild cards KW - pattern matching with k mismatches and don’t cares SP - 78 EP - 82 JF - Information processing letters VL - 118 N2 - 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 [Formula: see text]. With don't cares in the pattern, the best deterministic algorithm has a runtime of O(nk polylog m). 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 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 [Formula: see text] time. If the number of islands q is O(k) this runtime becomes [Formula: see text], 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(k2), this algorithm is asymptotically faster than the previous best algorithm for pattern matching with k mismatches with don't cares in the pattern. SN - 0020-0190 UR - https://www.unboundmedicine.com/medline/citation/28630523/On_pattern_matching_with_k_mismatches_and_few_don't_cares_ L2 - https://www.ncbi.nlm.nih.gov/pmc/articles/pmid/28630523/ DB - PRIME DP - Unbound Medicine ER -
Try the Free App:
Prime PubMed app for iOS iPhone iPad
Prime PubMed app for Android
Prime PubMed is provided
free to individuals by:
Unbound Medicine.