Compact Enumeration of Maximal Closed Substrings in Run-Length Encoded Strings

Abstract

A string $w$ is closed if $|w|=1$, or if $w$ has a non-empty proper border occurring only as its prefix and suffix. A maximal closed substring (MCS) is a maximal occurrence of a closed string; equivalently, it is a maximal closed repeat (MCR). We study the problem of enumerating all MCS occurrences directly from the run-length encoding (RLE) of a string. For a string $T$ of length $n$ with RLE size $m$, we give a compact representation of all MCS occurrences whose worst-case size is $O(m^2)$, and show that this bound is tight for this representation. Our approach is based on a characterization of MCS occurrences in terms of consecutive occurrences of their longest borders, together with data structures built on the RLE of $T$. Denoting the resulting representation by $\mathcal{F}$, we compute it in $O(m{\log }^{2}m+|\mathcal{F}|\log m)$ time using $O(m)$ working space.

Accepted for SPIRE 2026