BuST: Bundled Suffix Trees

We introduce a data structure, the Bundled Suffix Tree (BUST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet 11 together with a non-transitive relation 48 among its letters. Following the path of a substring \u3b2 within a BUST, constructed over a text \u3b1 of length n, not only the positions of the exact occurrences of \u3b2 in \u3b1 are found (as in a ST), but also the positions of all the substrings \u3b21, \u3b22, \u3b23... that are related with \u3b2 via the relation 48 among the characters of 11, for example strings at a certain "distance" from \u3b2. A BuST contains O(n1+\u3b4) additional nodes O(n1+\u3b4) in probability, and is constructed in O(n1+\u3b4) steps. In the worst case it contains O(n2) nodes