Catalog Home Page

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.

Free to read: http://dx.doi.org/10.1016/0304-3975(92)90137-5
*No subscription required

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 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
Publisher: Elsevier BV
Copyright: © 1992 Published by Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27508
Item Control Page Item Control Page