The suffix tree [1]} and suffix array [2]}
have been, arguably, the most powerful and heavily used tools in
Stringology. The suffix tree of string \(S\)  is a compressed trie of all suffixes of \(S\) , and the suffix array of \(S\)  corresponds to a pre-order traversal of all the leaves of the suffix tree of \(S\) . The natural application of the suffix tree is for indexing, but it
has been used for many purposes. An incomplete list includes
approximate matching [3]}, [4]}, parameterized
matching [5]}, [6]}, [7]}, [8]}, [9]}, efficient
compression [10]}, [11]}, [12]}, [13]}, [14]}, [15]}, [16]}, [17]}, [18]}, [19]},
finding syntactic regularities in
strings [20]}, [21]}, [22]}, [23]}, [24]}, [25]}, [26]}, [27]}, [28]}, [29]}, [30]},
and much more.
