Optimal algorithms for computing the canonical form of a circular string

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.