Pattern Matching on Run-Length Grammar-Compressed Strings in Linear Time.
36th Annual Symposium on Combinatorial Pattern Matching,
LIPIcs Vol.331, pp.9:1-9:16
(2025), [peer-reviewed]
Event Date:
June 17-19, 2025
@ Università degli studi di Milano, Milano, Italy
- Milano, Italy
- CPM
Abstract / 概要
Run-length straight-line programs (RLSLPs) are a technique for grammar-based compression, allowing any string to be represented with optimal space for $\delta$, 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.