### Suffix Array

A suffix array is a sorted array of all suffixes of a given string.

**Any suffix tree based algorithm** can be replaced with an algorithm **that uses a suffix array** enhanced with additional information and solves the same problem in the same time complexity.

**Naive algorithm** for construction of suffix array is to consider all suffixes, sort them using a O(nLogn) sorting algorithm and while sorting, maintain original indexes. Time complexity is _O(n^{2} * Logn)__.

There is an advanced **nLogn Algorithm** algorithm available to read here. Basic idea is to “Sort according to first two characters” and then “according to first four character”.

Example question: **[Facebook] Query Search (HashMap, suffix array)**.