Journal article
Computing the cover array in linear time
Algorithmica, Vol.32(1), pp.95-106
2002
Abstract
Let x denote a given nonempty string of length n = |x| . A proper substring u of x is a proper cover of x if and only if every position of x lies within an occurrence of u within x . This paper introduces an array γ = γ[1..n] called the cover array in which each element γ[i] , 1 ≤ i ≤ n , is the length of the longest proper cover of x[1..i] or zero if no such cover exists. In fact it turns out that γ describes all the covers of every prefix of x . Several interesting properties of γ are established, and a simple algorithm is presented that computes γ on-line in Θ(n) time using Θ(n) additional space. Thus the new algorithm computes for all prefixes of x information that previous cover algorithms could compute only for x itself, and does so with no increase in space or time complexity.
Details
- Title
- Computing the cover array in linear time
- Authors/Creators
- Y. Li (Author/Creator) - McMaster UniversityW.F. Smyth (Author/Creator) - IBM (Canada)
- Publication Details
- Algorithmica, Vol.32(1), pp.95-106
- Publisher
- Springer Verlag
- Identifiers
- 991005540758707891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
376 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
- Computer Science, Software Engineering
- Mathematics, Applied
- ESI research areas
- Engineering