کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4609169 | 1338418 | 2010 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Hardness of comparing two run-length encoded strings Hardness of comparing two run-length encoded strings](/preview/png/4609169.png)
In this paper, we consider a commonly used compression scheme called run-length encoding. We provide both lower and upper bounds for the problems of comparing two run-length encoded strings. Specifically, we prove the 3sum-hardness for both the wildcard matching problem and the kk-mismatch problem with run-length compressed inputs. Given two run-length encoded strings of mm and nn runs, such a result implies that it is very unlikely to devise an o(mn)o(mn)-time algorithm for either of them. We then present an inplace algorithm running in O(mnlogm)O(mnlogm) time for their combined problem, i.e. kk-mismatch with wildcards. We further demonstrate that if the aim is to report the positions of all the occurrences, there exists a stronger barrier of Ω(mnlogm)Ω(mnlogm)-time, matching the running time of our algorithm. Moreover, our algorithm can be easily generalized to a two-dimensional setting without impairing the time and space complexity.
Journal: Journal of Complexity - Volume 26, Issue 4, August 2010, Pages 364–374