2026-07-24T17:10:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23103 2025-10-02T12:37:37Z ddc:004 open_access

Pattern Matching on Run-Length Grammar-Compressed Strings in Linear Time Iguchi, Yuto Yoshinaka, Ryo Shinohara, Ayumi pattern matching run-length straight-line programs compression suffix tree Run-length straight-line programs (RLSLPs) are a technique for grammar-based compression, allowing any string to be represented with optimal space for δ, the substring complexity of the string. We address the compressed pattern matching problem for RLSLPs: Given a compressed text in RLSLP format and an uncompressed pattern, determine if the pattern appears in the text. This paper proposes an algorithm that solves this problem in linear time with respect to the size of the grammar and the length of the pattern. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuto Iguchi and Ryo Yoshinaka and Ayumi Shinohara 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.9 urn:nbn:de:0030-drops-231034 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode