# Suffix arrays

Another way of searching for substrings

---

## Ternary Quicksort


---

Partition on one character of the pivot, at depth d (start with d = 0)
Do 3 recursive calls (< = >) [instead of the usual 2 (< >)]
For the equals section, go to depth d + 1.

Ternary quicksort is O(n log n) (worst case is O(n^2 log n))
Regular quicksort on strings is O(m n log n) (worst case is O(n^3 log n))

---

## Back To Suffix Arrays...

A suffix array is a way of preprocessing the searched string before matching patterns (recall in KMP we preprocess the pattern string)

---

Creating a suffix array:
1. Write out the suffices, including “$” which indicates the end of a string
2. Sort the suffices, along with their index
3. Store the array of indices.

---


---

What is the space complexity??

For string of length m:
Array of indices : array of ints => O(m) space complexity<!-- .element: class="fragment" data-fragment-index="1" -->

We don't need to store each substring, we can just store the indices!<!-- .element: class="fragment" data-fragment-index="1" -->

---

How does a suffix array help us?

We can use a suffix array on string S to create an index.
We use the index to locate every occurrence of substring pattern P within the string S.

Finding every occurrence of pattern == finding every suffix beginning with substring.

We can do this with binary search

---