A Concurrent Construction of the Generalized Suffix Tree for a Set of Strings

The suffix tree, a compacted tree representing all suffixes of a given string, is utilized in various applications such as string processing and data compression. The suffix tree can be extended to a data structure of a set of strings, called the generalized suffix tree. In this paper we consider the problem of constructing concurrently the generalized suffix tree. The previous algorithm constructs the generalized suffix tree by processing strings in backward direction. In most applications, strings are handled in forward direction, and thus the previous algorithm has some limits. We propose an algorithm for constructing concurrently the generalized suffix tree by processing strings in forward direction.