کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427155 | 686460 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Approximate pattern matching with k-mismatches in packed text Approximate pattern matching with k-mismatches in packed text](/preview/png/427155.png)
• New algorithms for string matching with k -mismatches in AC0AC0 and word-RAM models.
• Method based on packed strings.
• We achieve worst-case time sublinear in the text length for some parameters.
• The proposed method is adapted for several other string matching problems.
Given strings P of length m and T of length n over an alphabet of size σ, the string matching with k-mismatches problem is to find the positions of all the substrings in T that are at Hamming distance at most k from P. If T can be read only one character at the time the best known bounds are O(nklogk) and O(n+nk/wlogk) in the word-RAM model with word length w . In the RAM models (including AC0AC0 and word-RAM) it is possible to read up to ⌊w/logσ⌋ characters in constant time if the characters of T are encoded using ⌈logσ⌉ bits. The only solution for k -mismatches in packed text works in O((nlogσ/logn)⌈mlog(k+logn/logσ)/w⌉+nε) time, for any ε>0ε>0. We present an algorithm that runs in time O(n⌊w/(mlogσ)⌋(1+logmin(k,σ)logm/logσ)) in the AC0AC0 model if m=O(w/logσ) and T is given packed. We also describe a simpler variant that runs in time O(n⌊w/(mlogσ)⌋logmin(m,logw/logσ)) in the word-RAM model. The algorithms improve the existing bound for w=Ω(log1+ϵn), for any ϵ>0ϵ>0. Based on the introduced technique, we present algorithms for several other approximate matching problems.
Journal: Information Processing Letters - Volume 113, Issues 19–21, September–October 2013, Pages 693–697