Optimal Pattern Matching in LZW Compressed Strings
Paweł Gawrychowski · ACM Transactions on Algorithms · 2013
We consider the following variant of the classical pattern matching problem: given an uncompressed pattern p [1.. m ] and a compressed representation of a string t [1.. N ], does p occur in t ? When t is compressed using the LZW method, we are able to detect the occurrence in optimal linear time, thus answering a question of Amir et al. [1994]. Previous results implied solutions with complexities O ( n log m + m ) Amir et al. [1994], O ( n + m 1+ε ) [Kosaraju 1995], or (randomized) O ( n log Nn + m ) [Farach and Thorup 1995], where n is the size of the compressed representation of t . Our algorithm is conceptually simple and fully deterministic.