Fast canonization of circular strings

Abstract

A circular string A = (a1,...,an) is a string that has n equivalent linear representations Ai = ai,...,an,a1,...,ai-1 for i = 1,...,n. The ai's are assumed to be well ordered. We say that Ai < Aj if the word ai...ana1...ai-1 precedes the word aj...ana1...aj-1 in the lexicographic order, Ai ≤ Aj if either Ai < Aj or Ai = Aj. Ai0 is a minimal representation of A if Ai0 ≤ Ai for all 1 ≤ i ≤ n. The index i0 is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most n + ⌈ d 2⌉ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used. © 1981.