Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic

DOI10.1007/978-3-642-23719-5_36zbMath1347.68377arXiv1104.4203OpenAlexW1931463589MaRDI QIDQ3092248

Paweł Gawrychowski

Publication date: 16 September 2011

Published in: Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.4203

zbMATH Keywords

pattern matchingLempel-Ziv compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Related Items (7)

Comparison of LZ77-type parsings ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ A \textit{really} simple approximation of smallest grammar ⋮ Approximation of grammar-based compression via recompression ⋮ The complexity of compressed membership problems for finite automata ⋮ Computing the Antiperiod(s) of a String ⋮ Approximate pattern matching in LZ77-compressed texts

This page was built for publication: Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic