Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item 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