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.
*Subscription may be required
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|
|Copyright:||© 1994 Published by Elsevier B.V.|
|Item Control Page|
Downloads per month over past year