Pattern matching with don't cares and few errors

详细信息    查看全文

• 作者：Raphaë ; l Clifford ; Klim Efremenko ; Ely Porat ; Amir Rothschild
• 关键词：Pattern matching ; String algorithms ; Randomised algorithms ; Group testing
• 刊名：Journal of Computer and System Sciences
• 出版年：2010
• 出版时间：March 2010
• 年：2010
• 卷：76
• 期：2
• 页码：115-124
• 全文大小：288 K

文摘

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 Θ(nk²log²m) 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.