2026-07-22T13:49:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:798 2024-03-06T11:06:54Z ddc:004 open_access

Solving Classical String Problems an Compressed Texts Lifshits, Yury Pattern matching Compressed text How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an $O(n2*m)$ algorithm for pattern matching in LZ-compressed texts. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yury Lifshits 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06201.7 urn:nbn:de:0030-drops-7984 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.7 eng https://creativecommons.org/licenses/by/4.0/legalcode