We discuss an intrinsic generalization of the suffix tree, designed to index a string of length n which has a natural partitioning into m multi-character substrings or

Since traditional suffix tree construction algorithms rely heavily
on the fact that *all* suffixes are inserted, construction of a
word suffix tree is nontrivial, in particular when only O(m)
construction space is allowed. We solve this problem, presenting an
algorithm with O(n) expected running time. In general,
construction cost is Omega(n) due to the need of scanning the
entire input. In applications that require strict node ordering, an
additional cost of sorting O(m') characters arises, where m' is
the number of distinct words. In either case, this is a significant
improvement over previously known solutions.

Furthermore, when the alphabet is small, we may assume that the $n$ characters in the input string occupy o(n) machine words. We illustrate that this can allow a word suffix tree to be built in sublinear time.