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 ∑ together with a non-transitive relation ≈ among its letters. Following the path of a substring β within a BUST, constructed over a text α of length n, not only the positions of the exact occurrences of β in α are found (as in a ST), but also the positions of all the substrings β1, β2, β3... that are related with β via the relation ≈ among the characters of ∑, for example strings at a certain "distance" from β. A BuST contains O(n1+δ) additional nodes O(n1+δ) in probability, and is constructed in O(n1+δ) steps. In the worst case it contains O(n2) nodes.