Fast canonization of circular strings

DOI10.1016/0196-6774(81)90013-4MaRDI QIDQ3910014zbMATH OpenOpenAlexFDO

Authors Yossi Shiloach

Publication date 1981

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(81)90013-4

zbMATH Keywords

algorithmminimal starting point

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Cited in

(30)

• A linear time solution to the single function coarsest partition problem
• Optimal canonization of all substrings of a string
• Optimal algorithms for computing the canonical form of a circular string
• Efficient CRCW-PRAM algorithms for universal substring searching
• An efficient parallel algorithm for the single function coarsest partition problem
• Sorting strings and constructing digital search trees in parallel
• Computing the original eBWT faster, simpler, and with less memory
• An efficient generalized shift-rule for the prefer-max de Bruijn sequence
• The alternating BWT: an algorithmic perspective
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Linear computation of unbordered conjugate on unordered alphabet
• A note on a simple computation of the maximal suffix of a string
• Fast parallel Lyndon factorization with applications
• Computation of maximal determinants of binary circulant matrices
• A fast average case algorithm for lyndon decomposition
• Indexing Circular Patterns
• Finding the cyclic covers of a string
• Circle graph isomorphism in almost linear time
• Quantum algorithm for lexicographically minimal string rotation
• Near-optimal quantum algorithms for string problems
• Constructing and indexing the bijective and extended Burrows-Wheeler transform
• Finding the maximum suffix with fewer comparisons
• Algorithms for Galois words: detection, factorization, and rotation
• Finding the cyclic covers of a string
• A note on quantum divide and conquer for minimal string rotation
• Generic non-recursive suffix array construction
• Simple linear time algorithm for sorting strings in omega-order with applications
• A theory of ultimately periodic languages and automata with an application to time granularity
• An automata-theoretic approach to the word problem for \(\omega\)-terms over R
• Description and analysis of a bottom-up DFA minimization algorithm

This page was built for publication: Fast canonization of circular strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3910014)