After playing with suffix trees a little more, I need to make a correction:

This problem asks for subsequences rather than substrings. As a result, when adding a node to the "suffix tree", it will need to be added as the child of more nodes than it would if we were building an actual suffix tree.

This seems like the type of change that might make construction of the tree harder than O(n). In particular, it will violate the constraint that a suffix tree for a string of length n has only n leaves.