The Endpos Tree

The Aho-Corasick failure tree of the same string. A parent's border is a border of every child's, so a subtree sum over the link tree counts occurrences of the substrings that state represents.

The endpos containment tree. A parent's set of ending positions contains every child's, so a subtree sum over the link tree counts occurrences of the substrings that state represents.

The compressed trie of all suffixes of the string. A parent's prefix is a prefix of every child's, so a subtree sum over the link tree counts occurrences of the substrings that state represents.

The endpos containment tree. A parent's set of ending positions is disjoint from every child's, so a subtree sum over the link tree counts distinct substrings that state represents.