Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

An optimal algorithm to compute all the covers of a string

Moore, D. and Smyth, W.F. (1994) An optimal algorithm to compute all the covers of a string. Information Processing Letters, 50 (5). pp. 239-246.

[img]
Preview
PDF - Authors' Version
Download (194kB)
Link to Published Version: http://dx.doi.org/10.1016/0020-0190(94)00045-X
*Subscription may be required

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).

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1994 Published by Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27522
Item Control Page Item Control Page

Downloads

Downloads per month over past year