Maintenance status: I no longer actively maintain this software. Expect details here to be outdated.
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.
Docs
API documentation is available on Hackage.
Download
Install from Hackage. The Git repository lives at github.com/bos/suffixtree.