A Haskell library for lazy, efficient suffix tree construction, search, and traversal.
The implementation is based on the first of those described in the following paper:
- Robert Giegerich and Stefan Kurtz, “A comparison of imperative and purely functional suffix tree constructions“, Science of Computer Programming 25(2-3):187-218, 1995
The library includes functions for constructing, searching, and traversing suffix trees. It only constructs parts of the suffix tree as they are needed, thus avoiding unnecessary work. Construction typically takes O(n log n) time, with searches taking linear time.
API documentation is available here.
You can obtain releases from here:
The darcs source repository is available from here:
darcs get http://darcs.serpentine.com/suffixtree/