Verifying a Border Array in Linear Time

Abstract

A border of a string $x$ is a proper (but possibly empty) prefix of $x$ that is also a suffix of $x$. The $borderarray$ $\beta =\beta [1..n]$ of a string $x=x[1..n]$ is an array of nonnegative integers in which each element $\beta (i)$, $1\le i\le n$, is the length of the longest border of $x[1..i]$. In this paper, we first present a simple linear-time algorithm to determine whether or not a given array $y=y[1..n]$ of integers is a border array of some string on an alphabet of unbounded size, and then a slightly more complex linear-time algorithm for an alphabet of any given (bounded) size $\alpha$. We then consider the problem of generating all possible distinct border arrays of given length $n$ on a bounded or unbounded alphabet, and doing so in time proportional to the number of arrays generated. A previously published algorithm that claims to solve this problem in constant time per array generated is shown to be incorrect, and new algorithms are proposed. We conclude with an equally efficient on-line algorithm for this problem.