Example

$ \newcommand{\maxgap}{\textit{maxgap}}% \def\tpref{\mathit{pref}} \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} $

Simulating a run on $x=\sa{abababaaba}$, positions in the list $L$ for $\ell=1,2,3$ are shown on the last lines. The associated values of $\maxgap(L)$ are respectively $2$, $3$ and $3$. The condition of line 4 is first met when $\ell=3$, giving the shortest cover $\sa{aba}=x[0\dd 2]$.

$i$ 0 1 2 3 4 5 6 7 8 9

$x[i]$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{b}$ $\sa{a}$ $\sa{a}$ $\sa{b}$ $\sa{a}$

$\tpref[i]$ 10 0 5 0 3 0 1 3 0 1

$L-L[0]$ 0 2 4 6 7 9 10

$L-L[\leq1]$ 0 2 4 7 10

$L-L[\leq2]$ 0 2 4 7 10

Problem 45: List Algorithm for Shortest Cover

A cover of a non-empty word $x$ is one of its factors whose occurrences cover all positions on $x$. As such it is a repetitive element akin to a repetition. The problem shows how to compute the shortest cover of a word using its prefix table $\tpref$, instead of its border table as in Problem 20. The algorithm is simpler but uses linear extra memory space.

For each length $\ell$ of a prefix of $x$, let $L(\ell) = (i \mid \tpref[i]=\ell)$. Algorithm ShortestCover computes the length of the shortest cover of its input.

ShortestCover$(x \textrm{ non-empty word})$

    \begin{algorithmic}
  \STATE $L\leftarrow (0,1,\dots,|x|)$
  \FOR{$\ell\leftarrow 0$ \TO $|x|-1$}
    \STATE $\mbox{remove elements of } L(\ell-1) \mbox{ from } L$
    \IF{$maxgap(L)\leq\ell$}
      \RETURN{$\ell$}
    \ENDIF
\ENDFOR
    \end{algorithmic}

Show that Algorithm ShortestCover computes the length of the shortest cover of its input and if properly implemented runs in linear time.

$i$	0	1	2	3	4	5	6	7	8	9
$x[i]$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{b}$	$\sa{a}$	$\sa{a}$	$\sa{b}$	$\sa{a}$
$\tpref[i]$	10	0	5	0	3	0	1	3	0	1
$L-L[0]$	0		2		4		6	7		9	10
$L-L[\leq1]$	0		2		4			7			10
$L-L[\leq2]$	0		2		4			7			10

125 Problems in Text Algorithms

Example

Problem 45: List Algorithm for Shortest Cover