The DOI matches its Crossref record.
Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
Abstract
Countless variants of the Lempel-Ziv compression are widely used in many real-life applications. This paper is concerned with a natural modification of the classical pattern matching problem inspired by the popularity of such compression methods: given an uncompressed pattern p[1 .. m] and a Lempel-Ziv representation of a string t[1 .. N], does p occur in t? Farach and Thorup [5] gave a randomized O(nlog2 N/n +m) time solution for this problem, where n is the size of the compressed representation of t. Building on the methods of [3] and [6], we improve their result by developing a faster and fully deterministic O(n log N/n +m) time algorithm with the same space complexity. Note that for highly compressible texts, log N/n might be of order n, so for such inputs the improvement is very significant. A small fragment of our method can be used to give an asymptotically optimal solution for the substring hashing problem considered by Farach and Muthukrishnan [4].
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Lemma 2 (Gawrychowski (2011)) A word w of length n can be processed in O ( n ) time such that given any basic factor w [ i..i +2 k -1] , with k ≥ 0 , we can retrieve in O (1) time the range of the suffix array of w of suffixes starting with w [ i..i +2 k -1] .”
From Longest Gapped Repeats and Palindromes (2017) · cites this paper as Gawrychowski (2011)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
No references could be resolved yet.
Research works printed but not linked: 14
- Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in z-compressed files. In: SODA 1994: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 705–714. SIAM, Philadelphia (1994)
- Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000) · DOI
- Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the smallest grammar: Kolmogorov complexity in natural models. In: STOC 2002: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 792–801. ACM, New York (2002) · doi:10.1145/509907.510021
- Farach, M., Muthukrishnan, S.: Perfect hashing for strings: Formalization and algorithms. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol. 1075, pp. 130–140. Springer, Heidelberg (1996) · doi:10.1007/3-540-61258-0_11
- Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. In: STOC 1995: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 703–712. ACM, New York (1995) · doi:10.1145/225058.225288
- Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. In: SODA 2011: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011) · doi:10.1137/1.9781611973082.29
- Iacono, J., Özkan, Ö.: Mergeable dictionaries. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 164–175. Springer, Heidelberg (2010) · doi:10.1007/978-3-642-14165-2_15
- Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918–936 (2006) · DOI
- Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249–260 (1987) · DOI · Paper page
- Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci. 298, 253–272 (2003) · doi:10.1016/s0304-3975(02)00426-7
- Kosaraju, S.R.: Pattern matching in compressed texts. In: Thiagarajan, P.S. (ed.) FSTTCS 1995. LNCS, vol. 1026, pp. 349–362. Springer, Heidelberg (1995) · doi:10.1007/3-540-60692-0_60
- Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1-3), 211–222 (2003) · doi:10.1016/s0304-3975(02)00777-6
- Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249–260 (1995) · DOI · Paper page
- Yao, A.C.C.: Lower bounds for algebraic computation trees with integer inputs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 308–313. IEEE Computer Society, Washington, DC, USA (1989) · doi:10.1109/sfcs.1989.63495
Cited by
Longest Gapped Repeats and Palindromes
Dumitran, M., Gawrychowski, P., & Manea, F. (2017) · Discrete Mathematics & Theoretical Computer Science · doi:10.23638/dmtcs-19-4-4 · Cited by 11
Self-citation
Metadata
- Authors
- Gawrychowski, P.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2011
- Pages
- 421-432
- ISSN
- 0302-9743
- 1611-3349
- Cited by
- 18
- References
- 0
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic. https://app.cochat.ai/papers/10.1007/978-3-642-23719-5_36
- The paper
- Gawrychowski, P. (2011). Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-642-23719-5_36
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.