  An \emph{indeterminate string} $x = x[1..n]$ on an alphabet $\Sigma$ is a
sequence of nonempty subsets of $\Sigma$; $x$ is said to be \emph{regular} if
every subset is of size one. A proper substring $u$ of regular $x$ is said to
be a \emph{cover} of $x$ iff for every $i \in 1..n$, an occurrence of $u$ in
$x$ includes $x[i]$. The \emph{cover array} $\gamma = \gamma[1..n]$ of $x$ is
an integer array such that $\gamma[i]$ is the longest cover of $x[1..i]$.
Fifteen years ago a complex, though nevertheless linear-time, algorithm was
proposed to compute the cover array of regular $x$ based on prior computation
of the border array of $x$. In this paper we first describe a linear-time
algorithm to compute the cover array of regular string $x$ based on the prefix
table of $x$. We then extend this result to indeterminate strings.

Data Structures and Algorithms