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

Computing the covers of a string in linear time

Moore, D. and Smyth, W.F. (1994) Computing the covers of a string in linear time. In: Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 23 - 25 January 1994, Arlington, Virginia

[img]
Preview
Link to Published Version: http://dl.acm.org/citation.cfm?id=314636&CFID=6911...
*Subscription may be required

Abstract

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 \Theta(n). By avoiding unnecessary checks, this algorithm appears to execute more quickly than that given in [2]. Let x denote a string of length n = jxj 0; in particular, let ffl denote the empty string of zero length. For any nonempty string x, let k 1 be the greatest integer such that (1:1) x = (v...

Item Type: Conference Paper
URI: http://researchrepository.murdoch.edu.au/id/eprint/27512
Item Control Page Item Control Page

Downloads

Downloads per month over past year