The suffix tree is a fundamental data structure when it comes to string algorithms. It captures the structure of a string via all the string’s suffixes and uses this structure as the basis of many algorithms. We will only use it for searching, where it provides linear search for a pattern after a linear preprocessing of the string we search in.
Imagine that you have listed all the suffixes of a string x$ with the sentinel $ (which in C is usually, and always in this chapter, zero). The sentinel is important here and you must always include it in suffix trees. So, we have the suffixes x$[0, n + 1], ...
