Computing the Cover Array in Linear Time

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 …