Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item 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