Campus Event Calendar
Event Entry
What and Who
Tying up the loose ends in fully LZW-compressed pattern matching
Pawel Gawrychowski
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 9 December 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
I'll talk about the following problem: given a text t and a pattern p , both compresed using the LZW/LZ78 method, detect an occurrence of p in t (and find the leftmost, if any). It turns out that this problem can be solved in linear time in the compressed sizes of p and t (which can be as small as the square root of their original lengths). I'll start with the uncomprossed pattern case (which appeared at SODA'11) and then sketch some ideas behind extending this to the fully compressed case (which will appear at STACS'12).
Contact
Pawel Gawrychowski
--email hidden
passcode not visible
logged in users only
Pawel Gawrychowski, 11/29/2011 13:55 -- Created document.