2014/12/09 by Alatabbi, Ali, Rahman, M. Sohel, Smyth, W. F.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1412.3016
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 proposed to compute the cover array of regular x based on prior computation of the border array of x. In this paper we first describe a linear-time algorithm to compute the cover array of regular string x based on the prefix table of x. We then extend this result to indeterminate strings.