CLR cover
Previous problem

Problem 141: Two problems on run-length encoded words

Next problem

The run-length encoding of a binary word $x\in\sa{1}\{\sa{0},\sa{1}\}^*$ is $$\RLE(x)= \sa{1}^{p_0}\sa{0}^{p_1}\cdots \sa{1}^{p_{s-2}}\sa{0}^{p_{s-1}},$$ where $s-2\geq0$, $p_i\gt 0$ for $i=0,\dots,s-2$ and $p_{s-1}\geq 0$. The value $|\RLE(x)|$ denotes the size of the compressed version of $x$. Note the length $|x|$ can be exponential w.r.t. $\RLE(x)$.

A cover of a non-empty word $x$ is one of its factors whose occurrences cover all positions on $x$. We refer to Problem 45 where a list-oriented computation of covers in standard strings is presented using the prefix table of the word (see Problem 22). Our algorithm here follows similar lines, except that now it operates on sparse sets of (well chosen) positions.

Let $x$ be a word whose $\RLE(x)$ is of size $n$. Show how to compute in linear time $O(n)$ the length of the shortest cover of $x$, assuming the cost of each arithmetic operation is a constant.

Extend the list-based algorithm for shortest covers in Problem 45 and the sparse prefix table.

Let a pattern $x$ and a text $y$ given in $\RLE$-form of total size $n$. Show how to check if $x$ occurs in $y$ in $O(n)$ time.