Conference paper
Computing the covers of a string in linear time
Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, Virginia, 23/01/1994–25/01/1994)
1994
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...
Details
- Title
- Computing the covers of a string in linear time
- Authors/Creators
- D. Moore (Author/Creator)W.F. Smyth (Author/Creator)
- Conference
- Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, Virginia, 23/01/1994–25/01/1994)
- Identifiers
- 991005540290607891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Conference paper
Metrics
89 File views/ downloads
75 Record Views