CLR cover
Previous problem

Problem 45: List Algorithm for Shortest Cover

Next problem

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.