Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949997 | Discrete Applied Mathematics | 2016 | 8 Pages |
Abstract
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 x based on the prefix table of x. We then extend this result to indeterminate strings.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ali Alatabbi, M. Sohel Rahman, W.F. Smyth,