Compressed and fully compressed pattern matching in one and two dimensions
Wojciech Rytter · Proceedings of the IEEE · 2000
We survey the complexity issues related to several algorithmic problems for compressed and fully compressed pattern matching in one- and two-dimensional texts without explicit decompression. Several related problems for compressed strings and arrays are considered: equality testing, computation of regularities, subsegment extraction, language membership, and solvability of word equations.