A New merging Algorithm for Constructing suffix Trees for Integer Alphabets
Dong‐Kyu Kim, Jeong Seop Sim, Kun-Soo Park · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2002
A new approach of constructing a suffix tree for the given string S is to construct recursively a suffix tree for odd positions construct a suffix tree for even positions from and then merge and into To construct suffix trees for integer alphabets in linear time had been a major open problem on index data structures. Farach used this approach and gave the first linear-time algorithm for integer alphabets The hardest part of Farachs algorithm is the merging step. In this paper we present a new and simpler merging algorithm based on a coupled BFS (breadth-first search) Our merging algorithm is more intuitive than Farachs coupled DFS (depth-first search ) merging and thus it can be easily extended to other applications.