Conference paper
Verifying a border array in linear time
10th Australasian Workshop on Combinatorial Algorithms (AWOCA) 1999 (Perth, Western Australia)
1999
Abstract
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.
Details
- Title
- Verifying a border array in linear time
- Authors/Creators
- F. Franěk (Author/Creator)W. Lu (Author/Creator)P.J. Ryan (Author/Creator)W.F. Smyth (Author/Creator)Y. Sun (Author/Creator)L. Yang (Author/Creator)
- Conference
- 10th Australasian Workshop on Combinatorial Algorithms (AWOCA) 1999 (Perth, Western Australia)
- Identifiers
- 991005543616507891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
157 File views/ downloads
92 Record Views