# 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.