Abstract
Hon et al. (2011) proposed a variant of the suffix tree, called circular suffix tree, and showed that it can be stored succinctly and can be used to solve the circular dictionary matching problem efficiently. In this paper, we give the first construction algorithm for the circular suffix tree, which takes O(nlogn) time and requires O(n log σ + d log n) bits of working space, where n is the total length of the patterns in D, d is the number of patterns in D, and σ is the alphabet size. © 2013 Springer-Verlag.