Catalog Home Page

Verifying a border array in linear time

Franěk, F., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y. and Yang, L. (1999) Verifying a border array in linear time. In: 10th Australasian Workshop on Combinatorial Algorithms (AWOCA) 1999, Perth, Western Australia



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.

Publication Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year