Back to Search
Start Over
Hardness of comparing two run-length encoded strings
- Source :
-
Journal of Complexity . Aug2010, Vol. 26 Issue 4, p364-374. 11p. - Publication Year :
- 2010
-
Abstract
- Abstract: 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 -mismatch problem with run-length compressed inputs. Given two run-length encoded strings of and runs, such a result implies that it is very unlikely to devise an -time algorithm for either of them. We then present an inplace algorithm running in time for their combined problem, i.e. -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 -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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0885064X
- Volume :
- 26
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Journal of Complexity
- Publication Type :
- Academic Journal
- Accession number :
- 52316830
- Full Text :
- https://doi.org/10.1016/j.jco.2010.03.003