CLR cover

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.