Space-Efficient Construction Algorithm for the Circular Suffix Tree

Hon et al. (2011) recently proposed a variant of suffix tree, called circular suffix tree, and showed that it can be compressed into succinct space and can be used to solve the circular dictionary matching problem efficiently. Although there are several efficient construction algorithms for the suffix tree in the literature, none of them can be applied directly to construct circular suffix tree due to the different nature of the patterns being indexed. Here, we give the first construction algorithm for the circular suffix tree, which takes O(n log n) time and requires O(n log σ + d log n)$ bits of working space, where n denotes the total length of the patterns in the dictionary, d denotes the number of patterns, and s denotes the alphabet size.