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.
Similar content being viewed by others
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Li, Smyth Computing the Cover Array in Linear Time . Algorithmica 32, 95–106 (2002). https://doi.org/10.1007/s00453-001-0062-2
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0062-2