Catalog Home Page

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

Publication 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