Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts

In this work, we study IPM queries on compressed and dynamic strings. Our result is an O(log n)-time query algorithm applicable to any balanced recompression-based run-length straight-line program (RLSLP).
In particular, one can use it on top of the RLSLP of Kociumaka, Navarro, and Prezza [IEEE TIT'23], whose size O(δ log (n * log σ)/(δ log n)) is optimal (among all text representations) as a function of the text length n, the alphabet size σ, and the substring complexity δ.
Our procedure does not rely on any preprocessing of the underlying RLSLP, which makes it readily applicable on top of the dynamic strings data structure of Gawrychowski, Karczmarz, Kociumaka, Łącki and Sankowski [SODA'18], which supports fully persistent updates in logarithmic time with high probability.

This talk is based on a joint paper with Tomasz Kociumaka; and the preparation for presenting that paper at SPIRE'2024.