Optimal algorithms for computing the canonical form of a circular string

DOI10.1016/0304-3975(92)90137-5zbMath0747.68029OpenAlexW1969428672MaRDI QIDQ1190455

Costas S. Iliopoulos, W. F. Smyth

Publication date: 26 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90137-5

zbMATH Keywords

canonical formCRCW PRAMleast lexicographic rotation of a circular string

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (12)

Parallel RAM algorithms for factorizing words ⋮ An efficient parallel algorithm for the single function coarsest partition problem ⋮ On the language of primitive words ⋮ Sorting strings and constructing digital search trees in parallel ⋮ A linear partitioning algorithm for hybrid Lyndons using \(V\)-order ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Near-optimal quantum algorithms for string problems ⋮ Towards optimal packed string matching ⋮ String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time ⋮ Generic Algorithms for Factoring Strings ⋮ Lyndon-like and V-order factorizations of strings ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel construction of a suffix tree with applications
• Lexicographically least circular substrings
• An improved algorithm to check for polygon similarity
• Factorizing words over an ordered alphabet
• Fast canonization of circular strings
• Fast Pattern Matching in Strings
• Fast parallel Lyndon factorization with applications

This page was built for publication: Optimal algorithms for computing the canonical form of a circular string