Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings

For a string $S$, a palindromic substring $S[i\mathrm{.}\mathrm{.}j]$ is said to be a \emph{shortest unique palindromic substring} ($SUPS$) for an interval $[s,t]$ in $S$, if $S[i\mathrm{.}\mathrm{.}j]$ occurs exactly once in $S$, the interval $[i,j]$ contains $[s,t]$, and every palindromic substring containing $[s,t]$ which is shorter than $S[i\mathrm{.}\mathrm{.}j]$ occurs at least twice in $S$. In this paper, we study the problem of answering $SUPS$ queries on run-length encoded strings. We show how to preprocess a given run-length encoded string ${RLE}_S$ of size $m$ in $O(m)$ space and $O(m \log \sigma_{$RLE${S}} + m \sqrt{\log m / \log\log m})$timesothatall$$SUPSs$$ for any subsequent query interval can be answered in $O(\sqrt{\log m / \log\log m} + \alpha)$time,where$\alpha$isthenumberofoutputs,and$\sigma{$RLE${S}}$isthenumberofdistinctrunsof$$RLE${S}$. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in $O(\sqrt{\log\log m /\log\log\log m}

• \alpha)$timeandcanbebuiltin$O(m \log \sigma_{$RLE${S}} + m \sqrt{\log m / \log\log m})$time,andthesecondoneanswersqueriesin$O(\log \log m + \alpha)$timeandcanbebuiltin$O(m \log \sigma{$RLE$_{S}})$time\mathrm{.}Bothofthesedatastructuresrequire$O(m)$ space.