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 it within x. This paper introduces an array gamma = gamma [1..n] called the cover array in which each element gamma [i], 1 less than or equal to i less than or equal to 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 gamma describes all the covers of every prefix of x, Several interesting properties of gamma are established, and a simple algorithm is presented that computes gamma on-line in Theta (n) time using Theta (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.
cover string algorithm word period quasiperiod