Provides algorithm to construct suffix tree.
Suffix tree for the string S of length n is defined as a tree such that:
- the paths from the root to the leaves have a one-to-one relationship with the suffixes of S,
- edges spell non-empty strings,
- and all internal nodes (except perhaps the root) have at least two children.
Since such a tree does not exist for all strings, S is padded with a terminal symbol not seen in the string (usually denoted $).
This ensures that no suffix is a prefix of another, and that there will be n leaf nodes, one for each of the n suffixes of S.
Since all internal non-root nodes are branching, there can be at most n − 1 such nodes, and n + (n − 1) + 1 = 2n nodes in total.
All internal nodes and leaves have incoming edge, so number of edges equal to number of leaves plus number of inner nodes,
thus at most 2n - 1.
Construction takes O(n) time.
This implementation was adapted from Java-port of
Mark Nelson's C++ implementation of Ukkonen's algorithm.