Suffix Array

Introduction

The suffix array stores all suffixes of a string in lexicographic order. It turns many string questions into array questions: substring search becomes binary search, repeated substrings become neighboring suffix comparisons, and the longest common prefix array can answer similarity queries.

We will build it with the prefix-doubling algorithm in $O(n \log n)$.

Problem or motivation

For a string $s$ of length $n$, suffix $i$ is $s_i s_{i+1}\ldots s_n$. We need to print the starting positions of all suffixes in lexicographic order.