Optimal algorithms for computing the canonical form of a circular string
Iliopoulos, C.S. and Smyth, W.F. (1992) Optimal algorithms for computing the canonical form of a circular string. Theoretical Computer Science, 92 (1). pp. 87-105.
*No subscription required
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 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 processors.
|Publication Type:||Journal Article|
|Copyright:||© 1992 Published by Elsevier B.V.|
|Item Control Page|