用户名: 密码: 验证码:
Set Intersection and Sequence Matching with mismatch counting
详细信息    查看全文
文摘
In the classical pattern-matching problem, one is given a text and a pattern both of which are sequences of letters. The requirement is to find all occurrences of the pattern in the text. We studied two modifications of the classical problem, where each letter in the text and pattern is a set (Set Intersection Matching problem) or a sequence (Sequence Matching problem). Two “letters” are found to match if the intersection of the corresponding sets is not empty or if the two sequences have a common element in the same index. We first show that the two problems are similar by establishing a linear time reduction between them. We then show the first known non-trivial and efficient algorithms for these problems, when the maximum set/sequence size d is small. The first is a Monte Carlo randomized algorithm for Set Intersection Matching  , that takes Θ(4dnlog⁡nlog⁡m) time, where n and m   are the lengths of the text and the pattern, respectively; the failure probability is less than View the MathML source. This algorithm can also be used, with slight modifications, when up to k   mismatches is allowed. In addition, it can be used to maintain an approximation of factor 1±ϵ of the mismatch count in View the MathML source time; the failure probability is bounded by View the MathML source. The second is a deterministic algorithm for Set Intersection Matching   that can be used to count the number of matches at each index of the text in a total running time View the MathML source, where σ is the size of the alphabet. The third algorithm, also deterministic, solves the Sequence Matching   problem in Θ(4dnlog⁡m) time.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700