Journal article
Computing covers using prefix tables
Discrete Applied Mathematics, Vol.212, pp.2-9
2015
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.
Details
- Title
- Computing covers using prefix tables
- Authors/Creators
- A. Alatabbi (Author/Creator)M. Sohel Rahman (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Discrete Applied Mathematics, Vol.212, pp.2-9
- Publisher
- Elsevier BV
- Identifiers
- 991005543004907891
- Copyright
- © 2015 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
101 File views/ downloads
52 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Mathematics, Applied
- ESI research areas
- Engineering