Pattern matching with don't cares and few errors

R Clifford, Efremenko Klim, Porat Ely, Rothschild Amir

Research output: Contribution to journalArticle (Academic Journal)peer-review

36 Citations (Scopus)


We present solutions for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern pof length m with don't care symbols and a bound k, our algorithms find all the places that the pattern matches the text with at most k mismatches. We first give a Θ(n(k+logmlogk)logn) time randomised algorithm which finds the correct answer with high probability. We then present a new deterministic Θ(nk2log2m) time solution that uses tools originally developed for group testing. Taking our derandomisation approach further we develop an approach based on k-selectors that runs in Θ(nkpolylogm) time. Further, in each case the location of the mismatches at each alignment is also given at no extra cost. Keywords: Pattern matching; String algorithms; Randomised algorithms; Group testing
Translated title of the contributionPattern matching with don't cares and few errors
Original languageEnglish
Pages (from-to)115 - 125
Number of pages11
JournalJournal of Computer and System Sciences
Publication statusPublished - Mar 2010


Dive into the research topics of 'Pattern matching with don't cares and few errors'. Together they form a unique fingerprint.

Cite this