Computing covers using prefix tables

An indeterminate string x=x[1..n] on an alphabet Σ is a sequence of nonempty subsets of Σ; x is said to be regular if every subset is of size one. A proper substring u of regular x is said to be a cover of x iff for every i∈1..n, an occurrence of u in x includes x[i]. The cover array γ=γ[1..n] of x is an integer array such that γ[i] is the longest cover of x[1..i]. Fifteen years ago a complex, though nevertheless linear-time, algorithm was …