Additional Problem 19: Covers in Run-Length-Encoded words
\(
\def\sa#1{\tt{#1}}
\def\RLE{\mathit{RLE}}
\)
Recall that the run-length encoding of a binary word
$w\in\sa{1}\{\sa{0},\sa{1}\}^*$ is
$$\RLE(w)= \sa{1}^{p_0}\sa{0}^{p_1}\cdots \sa{1}^{p_{n-2}}\sa{0}^{p_{n-1}},$$
where $n-2\geq0$, $p_i\gt 0$ for $i=0,\dots,n-2$ and
$p_{n-1}\geq0$.
We denote by $s=|\RLE(w)|$ the size
of the compressed version of $w$.
Given $\RLE(w)$ of size $n$.
Compute in linear time the length of the shortest cover of $w$.
Extend the list-based algorithm for shortest covers, use
the "compressed" table of prefixes of $O(n)$ size.