Catalog Home Page

Computing the cover array in linear time

Li, Y. and Smyth, W.F. (2002) Computing the cover array in linear time. Algorithmica, 32 (1). pp. 95-106.

[img]
Preview
PDF - Authors' Version
Download (280kB)
Link to Published Version: http://dx.doi.org/10.1007/s00453-001-0062-2
*Subscription may be required

Abstract

Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.

Publication Type: Journal Article
Publisher: Springer Verlag
URI: http://researchrepository.murdoch.edu.au/id/eprint/27858
Item Control Page Item Control Page

Downloads

Downloads per month over past year