The idea: sort all the suffixes once

A suffix of a text is the part from some position to the end. The suffix array lists the start positions of all suffixes in sorted (alphabetical) order. For banana$ the sorted suffixes are $, a$, ana$, anana$, banana$, na$, nana$, so SA = [6, 5, 3, 1, 0, 4, 2]. It is just n integers, yet it answers "where does this pattern occur?" for any pattern.

The seven suffixes of banana$ listed in text order on the left and in sorted order on the right, with the suffix array column 6 5 3 1 0 4 2 and the LCP column – 0 1 3 0 0 2; the rows ana$ and anana$ share the prefix ana
Sorting the suffixes gives SA; neighbours in the sorted list share prefixes, which the LCP column counts.

The text ends with a sentinel $ that is smaller than every letter and occurs nowhere else. Then no suffix is a prefix of another, and any two suffixes differ at some character. In the animation each row is one suffix: the SA[k] cell is its start position and k is its row number.

Building it: prefix doubling

Sorting n suffixes with ordinary string comparisons can cost O(n² log n). Prefix doubling (Manber and Myers, 1990) ranks suffixes by longer and longer prefixes instead:

  1. Round 0: rank[i] = the order of the first character T[i].
  2. Round k (k = 1, 2, 4, …): give suffix i the pair (rank[i], rank[i+k]). The first part ranks its first k characters, the second part ranks the next k, so the pair ranks the first 2k characters. A suffix too short for the second part gets –, which sorts first.
  3. Sort by the pairs and give equal pairs equal new ranks.
  4. Stop when all n ranks differ.

The number of characters compared doubles every round, so at most ⌈log₂ n⌉ rounds are needed. With radix sort on the pairs each round is O(n), and the whole build is O(n log n). In the animation, orange ranks are still tied and green ranks are final. (Demo 1: build banana$; Demo 5: aaaaaaaa needs three doubling rounds, because its suffixes agree on long prefixes.)

Ranks of the suffixes of banana$ after each round: by 1 character there are 4 distinct ranks, by 2 characters 5, by 4 characters all 7 are distinct, so the order is final after round 2
Each round doubles the prefix the ranks stand for; banana$ is fully sorted after ranking by 4 characters.

The LCP array and Kasai's algorithm

LCP[k] is the length of the longest common prefix of the suffixes in rows k − 1 and k. Comparing every pair of neighbours from scratch can take O(n²). Kasai's algorithm (2001) does it in O(n) by visiting the suffixes in text order i = 0, 1, 2, … instead of row order. It needs rank[i], the row of suffix i, which is the inverse of SA.

The key fact: if suffix i shares h characters with the row above it, then suffix i + 1 (the same string without its first character) shares at least h − 1 characters with the row above it. So the counter h never restarts from 0; it drops by at most one per step and rises at most n times in total, for at most 2n character comparisons. In the animation the carried-over characters are blue (skipped), new matches green, the mismatch red. (Demo 2)

kasai(T, SA):
    for k = 0 to n − 1: rank[SA[k]] = k
    h = 0
    for i = 0 to n − 1:                     // text order
        if rank[i] == 0: h = 0; continue    // row 0 has no row above
        j = SA[rank[i] − 1]                 // the suffix in the row above
        while T[i + h] == T[j + h]: h = h + 1
        LCP[rank[i]] = h
        if h > 0: h = h − 1                 // the next suffix keeps h − 1

A pattern P occurs at position i exactly when the suffix starting at i begins with P. Because the rows are sorted, all suffixes that begin with P sit next to each other. One binary search finds the first row ≥ P, a second finds the first row whose first m characters are > P; the rows in between are every occurrence, and SA turns them into text positions. Each step compares at most m characters, so a search costs O(m log n), however long the text is. (Demo 3: "ana" finds rows 2–3, the overlapping matches at 1 and 3; Demo 4: "nab" is not found.)

Sorted suffixes of banana$ with the rows ana$ and anana$ highlighted as the block that starts with ana; the lower bound points at row 2, the upper bound at row 4, and SA maps the block to text positions 3 and 1
Every match of P is a prefix of a suffix, so the matches form one block of rows found by two binary searches.

Compare this with KMP and the other matchers in the String Search Race, which scan the whole text for each pattern: the suffix array pays O(n log n) once, then every query is independent of n.

What else the two arrays give

QuestionAnswer from SA and LCP
Longest repeated substringThe largest LCP value and its two rows (Demo 6: "issi" in mississippi)
Number of distinct substringsn(n+1)/2 minus the sum of the LCP values (counting without the sentinel)
Longest common substring of A and BBuild on A#B$; the largest LCP between rows from different strings
Burrows–Wheeler transform (bzip2, FM index)The character before each suffix, read in SA order

A trie of all suffixes (a suffix tree, once compressed) answers the same questions, but uses many pointers per character. A suffix array stores one integer per character and is the usual choice for large texts such as genomes.

next to the repeated-substring / LCP discussion, add "Compressors such as LZ77 look for repeats in a sliding window instead: see LZ77 and DEFLATE.

What the page leaves out

Linear-time constructions (SA-IS, DC3/skew) used by real libraries; the radix sort inside each doubling round (the page sorts the pairs directly); searches sped up with LCP information to O(m + log n); enhanced suffix arrays and the FM index, which compress the text and still search it; and large alphabets, where the initial ranks come from sorting the distinct characters.