Journal article
Weak repetitions in strings
Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.24, pp.33-48
1997
Abstract
A weak repetition in a string consists of two or more adjacent substrings which are permutations of each other. We describe a straightforward \Theta(n 2 ) algorithm which computes all the weak repetitions in a given string of length n defined on an arbitrary alphabet A. Using results on Fibonacci and other simple strings, we prove that this algorithm is asymptotically optimal over all known encodings of the output.
Details
- Title
- Weak repetitions in strings
- Authors/Creators
- L.J. Cummings (Author/Creator)W.F. Smyth (Author/Creator)
- Publication Details
- Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.24, pp.33-48
- Publisher
- Charles Babbage Research Centre
- Identifiers
- 991005541366407891
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
- Publisher URL
- http://www.combinatorialmath.ca/jcmcc/
Metrics
121 File views/ downloads
75 Record Views