A COMPARISON OF IMPERATIVE AND PURELY FUNCTIONAL SUFFIX TREE CONSTRUCTIONS

We explore the design space of implementing suffix tree algorithms in the functional paradigm. We review the linear time and space algorithm s of McCreight and Ukkonen. Based on a new terminology of nested suffi xes and nested prefixes, we give a simpler and more declarative explan ation of these algorithms than was previously known. We design two ''n aive'' versions of these algorithms which are not linear time, but use simpler data structures, and can be implemented in a purely functiona l style. Furthermore, we present a new, ''lazy'' suffix tree construct ion which is even simpler. We evaluate both imperative and functional implementations of these algorithms. Our results show that the naive a lgorithms perform very favourably, and in particular, the lazy constru ction compares very well to all the others.