Optimal algorithms for computing the canonical form of a circular string

C.S. Iliopoulos; W.F. Smyth

doi:10.1016/0304-3975(92)90137-5

Back

Optimal algorithms for computing the canonical form of a circular string

Journal article

Peer reviewed

Optimal algorithms for computing the canonical form of a circular string

C.S. Iliopoulos and W.F. Smyth

Theoretical Computer Science, Vol.92(1), pp.87-105

1992

DOI: https://doi.org/10.1016/0304-3975(92)90137-5

Files and links (1)

url

Free to Read *No subscription requiredView

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.

Details

Title: Optimal algorithms for computing the canonical form of a circular string
Authors/Creators: C.S. Iliopoulos (Author/Creator)
W.F. Smyth (Author/Creator)
Publication Details: Theoretical Computer Science, Vol.92(1), pp.87-105
Publisher: Elsevier BV
Identifiers: 991005544996507891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

65 Record Views

15 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.1103 Efficient Algorithms
Web Of Science research areas: Computer Science, Theory & Methods
ESI research areas: Computer Science