Catalog Home Page

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

Publication 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