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

Abstract

Internal Pattern Matching (IPM) queries on a text $T$, given two fragments $X$ and $Y$ of $T$ such that $|Y|<2|X|$, ask to compute all exact occurrences of $X$ within $Y$. IPM queries have been introduced by Kociumaka, Radoszewski, Rytter, and Waleń [SODA'15 & SICOMP'24], who showed that they can be answered in $O(1)$ time using a data structure of size $O(n)$ and used this result to answer various queries about fragments of $T$. 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(\hat{I}´\log \frac{n\log \ddot{I}ƒ}{\hat{I}´\log n})$ is optimal (among all text representations) as a function of the text length $n$, the alphabet size $\ddot{I}ƒ$, and the substring complexity $\hat{I}´$. 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.

A preliminary version of this work was presented at SPIRE 2024