Journal article
An optimal algorithm to compute all the covers of a string
Information Processing Letters, Vol.50(5), pp.239-246
1994
Abstract
Let x denote a given nonempty string of length n = |x| ⩾ 1. A string u is a cover of x if and only if every position of x lies within an occurrence of u within x. Thus x is always a cover of itself. In this paper we characterize all the covers of x in terms of an easily computed normal form for x. The characterization theorem then gives rise to a simple recursive algorithm which computes all the covers of x in time Θ(n).
Details
- Title
- An optimal algorithm to compute all the covers of a string
- Authors/Creators
- D. Moore (Author/Creator) - Curtin UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Information Processing Letters, Vol.50(5), pp.239-246
- Publisher
- Elsevier BV
- Identifiers
- 991005545556507891
- Copyright
- © 1994 Published by Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
182 File views/ downloads
119 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, Information Systems
- ESI research areas
- Computer Science