Simple and efficient LZW-compressed multiple pattern matching
We consider a natural variant of the classical multiple pattern matching problem: given a LempelZivWelch representation of a string and a collection of (uncompressed) patterns, does any of them occur in the text? As shown by Kida et al. [15], extending the single pattern algorithm of Amir, Benson and Farach [2] gives a running time of O(n+M2) O ( n + M 2 ) for the more general case, where n is the number of codewords in the compressed representation of the text and M  is the sum of the length of all patterns. We prove that in fact it is possible to achieve O ( n log M + M ) or O(n+M1+?) O ( n + M 1 + ? ) complexity. While not linear, running times of our solutions match the single pattern bounds achieved by the previously known solutions [2]and[17] in a more structured and unified manner, and without using any combinatorics on words. The only nontrivial components of our method are suffix arrays, constant time range minimum queries, and balanced binary search trees.
multiple pattern matching lempelzivwelch compression