Academic
Publications
Optimal pattern matching in LZW compressed strings

Optimal pattern matching in LZW compressed strings,Pawel Gawrychowski

Optimal pattern matching in LZW compressed strings  
BibTex | RIS | RefWorks Download
We consider the following variant of the classical pattern matching problem: given an uncompressed pattern s[1..m] and a compressed representation of a string t[1..N], does s 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, Benson, and Farach [2]. Previous results implied solutions with complexities O(n log m + m) [2], O(n + m1+ε) [14], or (randomized) O(n log N/n + m) [8], where n is the size of the compressed representation of t. Our algorithm is simple and fully deterministic.
Conference: ACM-SIAM Symposium on Discrete Algorithms - SODA , pp. 362-372, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.