Computing covers using prefix tables
Alatabbi, A., Sohel Rahman, M. and Smyth, W.F. (2015) Computing covers using prefix tables. Discrete Applied Mathematics, 212 . pp. 2-9.
*Subscription may be required
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..ni∈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.
Item Type: | Journal Article |
---|---|
Murdoch Affiliation(s): | School of Engineering and Information Technology |
Publisher: | Elsevier BV |
Copyright: | © 2015 Elsevier B.V. |
URI: | http://researchrepository.murdoch.edu.au/id/eprint/27326 |
![]() |
Item Control Page |
Downloads
Downloads per month over past year