Catalog Home Page

Verifying a border array in linear time

Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y. and Yang, L. (2002) Verifying a border array in linear time. Journal of Combinatorial Mathematics and Combinatorial Computing, 42 . pp. 223-236.


A border of a string x is a proper (but possibly empty) prefix of x that is also a suffix of x. The border array β = β[1..n] of a string x = x[1..n] is an array of nonnegative integers in which each element β[i], 1 ≤ i ≤ 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. We state as an open problem the design of a corresponding and equally efficient algorithm on an alphabet of bounded size α. 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 state as open the design of an equally efficient on-line algorithm for this problem.

Item Type: Journal Article
Publisher: Charles Babbage Research Centre
Publishers Website:
Item Control Page Item Control Page