Suffix arrays are a data structure which allow for efficient string matching and other operations. In this tutorial, we will describe what they are and why they are useful. We will also describe algorithms for generating suffix arrays, starting with a trivial one and moving onto faster ones. Lets get started.
What are suffix arrays?
Consider any string, say s = "random". It is customary to include a symbol at the end which is smaller than any character. Let us include '$', which is smaller than any Latin character in ASCII, so s = "random$".
Consider all suffixes of this string, and name the suffix that starts at the i-th position as z_i.
In this tutorial we will be discussing dynamic programming on trees, a very popular algorithmic technique that solves many problems involving trees. We'll be learning this technique by example. We'll take a problem solving approach in this tutorial, not just describing what the final solution looks like, but walking through how one might go about solving such problems.
A first example
Consider a tree in which every node has a positive value written on it. The task is to select several nodes from the tree (you may also select none), so that the sum of values of the nodes you select is maximized, and no two adjacent nodes are selected. The desired solution has complexity O(n).