A Suffix Tree is a compressed tree containing all the suffixes of the given (usually long) text string T of length n characters (n can be in order of hundred thousands characters).
The positions of each suffix in the text string T are recorded as integer indices at the leaves of the Suffix Tree whereas the path labels (concatenation of edge labels starting from the root) of the leaves describe the suffixes.
Suffix Tree provides a particularly fast implementation for many important (long) string operations.
This data structure is very related to the Suffix Array data structure. Both data structures are usually studied together.
The suffix i (or the i-th suffix) of a (usually long) text string T is a 'special case' of substring that goes from the i-th character of the string up to its last character.
For example, if T = "STEVEN$", then suffix 0 of T is "STEVEN$" (0-based indexing), suffix 2 of T is "EVEN$", suffix 4 of T is "EN$", etc.
The visualization of Suffix Tree of a string T is basically a rooted tree where path label (concatenation of edge label(s)) from root to each leaf describes a suffix of T. Each leaf vertex is a suffix and the integer value written inside the leaf vertex (we ensure this property with terminating symbol $) is the suffix number.
An internal vertex will branch to more than one child vertex, therefore there are more than one suffix from the root to the leaves via this internal vertex. The path label of an internal vertex is a common prefix among those suffix(es).
The Suffix Tree above is built from string T = "GATAGACA$" that have these 9 suffixes:
| i | Suffix |
|---|---|
| 0 | GATAGACA$ |
| 1 | ATAGACA$ |
| 2 | TAGACA$ |
| 3 | AGACA$ |
| 4 | GACA$ |
| 5 | ACA$ |
| 6 | CA$ |
| 7 | A$ |
| 8 | $ |
Now verify that the path labels of suffix 7/6/2 are "A$"/"CA$"/"TAGACA$", respectively (there are 6 other suffixes). The internal vertices with path label "A"/"GA" branch out to 4 suffixes {7, 5, 3, 1}/2 suffixes {4, 0}, respectively (we ignore the trivial internal vertex = root vertex that branches out to all 9 suffixes).
In order to ensure that every suffix of the input string T ends in a leaf vertex, we enforce that string T ends with a special terminating symbol '$' that is not used in the original string T and has ASCII value lower than the lowest allowable character in T (which is character 'A' in this visualization). This way, edge label '$' always appear at the leftmost edge of the root vertex of this Suffix Tree visualization.
For the Suffix Tree example above (for T = "GATAGACA$"), if we do not have terminating symbol '$', notice that suffix 7 "A" (without the '$') does NOT end in a leaf vertex and can complicate some operations later.
As we have ensured that all suffixes end at a leaf vertex, there are at most n leaves/suffixes in a Suffix Tree. All internal vertices (including the root vertex if it is an internal vertex) are always branching thus there can be at most n-1 such vertices, as shown with one of the extreme test case on the right.
The maximum number of vertices in a Suffix Tree is thus = n (leaves) + (n-1) internal vertices = 2n-1 = O(n) vertices. As Suffix Tree is a tree, the maximum number of edges in a Suffix Tree is also (2n-1)-1 = O(n) edges.
When all the characters in string T is all distinct (e.g., T = "ABCDE$"), we can have the following very short Suffix Tree with exactly n+1 vertices (+1 due to root vertex).
All available operations on the Suffix Tree in this visualization are listed below:
There are a few other possible operations of Suffix Tree that are not included in this visualization.
In this visualization, we only show the fully constructed Suffix Tree without describing the details of the O(n) Suffix Tree construction algorithm — it is a bit too complicated. Interested readers can explore this instead.
We limit the input to only accept 25 (cannot be too long due to the available drawing space — but in the real application of Suffix Tree, n can be in order of hundred thousand to million characters) ASCII (or even Unicode) characters. If you do not write a terminating symbol '$' at the back of your input string, we will automatically do so. If you place a '$' in the middle of the input string, they will be ignored. And if you enter an empty input string, we will resort to the default "GATAGACA$".
For convenience, we provide a few classic test case input strings usually found in Suffix Tree/Array lectures, but to showcase the strength of this visualization tool, you are encouraged to enter any 25-characters string of your choice (ending with character '$'). You can use Chinese characters (in Unicode), e.g., "四是四十是十十四不是四十四十不是十四$".
Assuming that the Suffix Tree of a (usually longer) string T (of length n) has been built, we want to find all occurrences of pattern/search string P (of length m).
To do this, we search for the vertex x in the suffix Tree of T which has path label (concatenation of edge label(s) from the root to x) where P is the prefix of that path label. Once we find this vertex x, all the leaves in the subtree rooted at x are the occurrences.
Time complexity: O(m+k) where k is the total number of occurrences.
For example, on the Suffix Tree of T = "GATAGACA$" above, try these scenarios:
Assuming that the Suffix Tree of a (usually longer) string T (of length n) has been built, we can find the Longest Repeated Substring (LRS) in T by simply finding the deepest (the one that has the longest path label) internal vertex of the Suffix Tree of T.
This is because each internal vertex of the Suffix Tree of T branches out to at least two (or more) suffixes, i.e., the path label (common prefix of these suffixes) are repeated.
The deepest (the one that has the longest path label) internal vertex is the required answer, which can be found in O(n) with a simple tree traversal.
Without further ado, try . We have LRS = "GA".
It is possible that T contains more than one LRS, e.g., try .
We have LRS = "ANA" (actually overlap) or "BAN" (without overlap).
This time, we need two input strings T1 and T2 that terminate with symbol '$'/'#', respectively. We then create the generalized Suffix Tree of these two strings T1+T2 in O(n) where n = n1+n2 (sum of the length of the two strings). We can find the Longest Common Substring (LCS) of those two strings T1 and T2 by simply finding the deepest and valid internal vertex of the generalized Suffix Tree of T1+T2.
To be a valid internal vertex for consideration as an LCS candidate, an internal vertex must represents suffixes from both strings, i.e., a common substring found in both T1 and T2.
Then, since an internal vertex of the Suffix Tree of T branches out to at least two (or more) suffixes, i.e., the path label (common prefix of these suffixes) are repeated. If that internal vertex is also a valid internal vertex, then it is a common substring that is repeated.
The valid and deepest (the one that has the longest path label) internal vertex is the required answer, which can be found in O(n) with a simple tree traversal.
Without further ado, try on the generalized Suffix Tree of string T1 = "GATAGACA$" and T2 = "CATA#" (notice that the UI will change to generalized Suffix Tree version). We have LCS = "ATA".
There are a few other things that we can do with Suffix Tree like "Finding Longest Repeated Substring without overlap", "Finding Longest Common Substring of ≥ 2 strings", etc, but we will keep that for later.
We will continue the discussion of this String-specific data structure with the more versatile to Suffix Array data structure.