Computing Covers Using Prefix Tables

Abstract

An \emph{indeterminate string} $x=x[\mathrm{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 \mathrm{1..}n$, an occurrence of $u$ in $x$ includes $x[i]$. The \emph{cover array} $\gamma =\gamma [\mathrm{1..}n]$ of $x$ is an integer array such that $\gamma [i]$ is the longest cover of $x[\mathrm{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.

14 pages, 1 figure