Journal article
Optimal algorithms for computing the canonical form of a circular string
Abstract
An O(log n) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using O(nlog n)processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(log n log log n) units of time, also using O(nlog n) processors.
Authors
Iliopoulos CS; Smyth WF
Journal
Theoretical Computer Science, Vol. 92, No. 1, pp. 87–105
Publisher
Elsevier
Publication Date
1 1992
DOI
10.1016/0304-3975(92)90137-5
ISSN
0304-3975