A support tool searches a 40 MB log for phrases analysts type: FATAL timeout, then connection reset, then the same phrases again. Each query calls indexOf and walks the haystack from scratch. The first search is honest. The twentieth is the same walk you already paid for.

A suffix array is the sorted list of a string’s suffixes, stored as start indices. You sort once. Each later query is a binary search over those suffixes — not a rescan of the text. Terms this series will not re-teach (ADT vs implementation, how to read a complexity table) live on the Data Structures Roadmap.

Suffixes as start indices

Every substring of a text is a prefix of some suffix. If you can find the suffixes that start with a pattern, you have found every occurrence.

You do not copy those suffixes. Copying banana into six new strings would be O(n²) characters. You keep the original text and an array of starting positions:

text = banana
index     suffix
    0     banana
    1     anana
    2     nana
    3     ana
    4     na
    5     a

The suffix array is those indices in lexicographic order of the suffixes they name:

sa = [5, 3, 1, 0, 4, 2]

5 → a
3 → ana
1 → anana
0 → banana
4 → na
2 → nana

Same characters. Different layout. The hot object is an int[] of length n, plus the string you already had.

Sort the indices

A teaching build sorts the n start positions with a comparator that walks the text. Each comparison can read up to n characters; there are O(n log n) comparisons. That is O(n² log n) time. Fine for a few thousand characters. Painful for a genome.

public final class SuffixArray {
    private final String text;
    private final int[] sa;

    public SuffixArray(String text) {
        this.text = text;
        this.sa = buildNaive(text);
    }

    public int[] indices() {
        return sa.clone();
    }

    private static int[] buildNaive(String s) {
        int n = s.length();
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (a, b) -> compareSuffixes(s, a, b));
        int[] sa = new int[n];
        for (int i = 0; i < n; i++) {
            sa[i] = idx[i];
        }
        return sa;
    }

    private static int compareSuffixes(String s, int i, int j) {
        int n = s.length();
        while (i < n && j < n) {
            int d = Character.compare(s.charAt(i), s.charAt(j));
            if (d != 0) {
                return d;
            }
            i++;
            j++;
        }
        return Integer.compare(n - i, n - j);
    }
}

Compare by index. Do not substring inside the comparator — that would allocate n new strings on top of the quadratic comparisons.

Note: Linear-time constructions exist (SA-IS, DC3). They are the right choice at millions of characters. This post will not implement them. The layout you search is the same int[] either way; only the build changes.

There is no java.util.SuffixArray. The JDK gives you String.indexOf and Pattern. A suffix array is a layout you build (or take from a library) when the same text will answer many substring queries.

Binary search for a pattern

The suffixes are sorted, so a pattern belongs in one contiguous range of sa. Binary search compares the pattern to the suffix at sa[mid]. Treat “pattern is a prefix of this suffix” as a match:

    public boolean contains(String pattern) {
        int lo = lowerBound(pattern);
        return lo < sa.length && prefixOfSuffix(pattern, sa[lo]);
    }

    private int lowerBound(String pattern) {
        int lo = 0;
        int hi = sa.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (comparePattern(pattern, sa[mid]) > 0) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    private int comparePattern(String pattern, int suffixStart) {
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        while (i < m && suffixStart + i < n) {
            int d = Character.compare(pattern.charAt(i), text.charAt(suffixStart + i));
            if (d != 0) {
                return d;
            }
            i++;
        }
        return i == m ? 0 : 1;
    }

    private boolean prefixOfSuffix(String pattern, int suffixStart) {
        return comparePattern(pattern, suffixStart) == 0;
    }

Each step reads at most m characters (m is the pattern length). The loop runs O(log n) times. The query is O(m log n) — n is no longer a linear scan.

Finding every start offset is a second bound: walk sa until the pattern is no longer a prefix. Those hits sit next to each other because equal prefixes sort together.

    public int[] occurrences(String pattern) {
        int lo = lowerBound(pattern);
        int hi = lo;
        while (hi < sa.length && prefixOfSuffix(pattern, sa[hi])) {
            hi++;
        }
        int[] hits = new int[hi - lo];
        for (int i = lo; i < hi; i++) {
            hits[i - lo] = sa[i];
        }
        return hits;
    }

On banana, contains("ana") is true. occurrences("ana") returns {3, 1} — the two suffixes that start with ana. contains("band") is false: no suffix has that prefix.

query "ana"   sa range [1, 3) → starts 3, 1
query "a"     sa range [0, 3) → starts 5, 3, 1
query "nan"   sa range [5, 6) → start  2
query "band"  empty

Sort once. Binary-search every later pattern. That is the whole machine. An LCP array (longest common prefix of adjacent suffixes) can speed some follow-on queries; it is an extra int[], not a different structure. You do not need it to answer “is this a substring” and “where.”

What the bill looks like

Read this as a shopping list, the way the roadmap taught: pick the structure whose expensive operations are ones you rarely perform.

Structure: suffix array
build (naive)     O(n² log n)   compare suffixes while sorting
build (SA-IS)     O(n)          mention only; not in this post
contains(p)       O(m log n)    binary search, m = |pattern|
occurrences(p)    O(m log n + k) k = number of hits
space             O(n)          n integers + the original string

Space is the selling point against a suffix tree: one integer per character, not a heap of nodes and child pointers. A 40 MB log needs about 40 MB extra for a 32-bit sa (UTF-16 Java String length, not bytes on disk — count text.length(), not file size, when you size the array).

Suffix trees: why they exist, why arrays often suffice

A suffix tree stores every suffix as a path from the root, with edges labeled by substrings and extra pointers (suffix links) so a linear-time construction can exist. Once built, a pattern of length m is a walk of O(m) edge labels — no log n binary search.

That is why the tree exists: some string algorithms want that walk, plus an explicit branching structure (repeated-substring detection, some DNA analyses, certain linear-time tricks). Ukkonen’s construction is the name you will hear. The bill is memory and code: nodes, edge maps or compressed labels, suffix links, and a construction that is easy to get wrong.

A suffix array is often enough because it stores the same sorted suffixes in n integers. Substring search is binary search, not a tree walk. If you later need tree-like operations, an LCP array plus the suffix array can simulate many of them without allocating the tree. Reach for the tree when you have a measured reason the extra pointers pay for themselves — not because the textbook drew the tree first.

When not to use a suffix array

Skip a suffix array when:

  • You will search the string once — text.indexOf(pattern) (or a single contains) is the layout. Building sa is more work than the walk you were going to do anyway.
  • The string is tiny — a few hundred characters, a config line, a username. Binary search over suffixes does not beat a scan you cannot feel. The index is ceremony.
  • The text mutates — inserts and deletes in the middle invalidate every index. You rebuild. If the haystack is a live buffer, you wanted a different design (streaming search, a rolling automaton), not a static suffix index.
  • The job is prefixes of many independent keys — product names, routes, dictionary words. That is a prefix tree of separate strings, not suffixes of one text.

A regex engine is also the wrong substitute when the pain is “this fixed substring, many times, same corpus.” Pattern compiles an automaton for a language. A suffix array indexes one string.

Cheat sheet

Layout:   int[] of suffix start indices, sorted by the suffixes they name
Insight:  every substring is a prefix of some suffix
Build:    naive O(n² log n); linear algorithms exist (SA-IS) — do not hand-roll
Query:    binary search; match = pattern is a prefix of sa[mid]
Hits:     a contiguous range of sa
Space:    O(n) integers + the original text
JDK:      no SuffixArray; indexOf is the one-shot tool
Tree:     same suffixes, heavier nodes; arrays are the usual index

Do:

  • Build a suffix array when one text must answer many substring queries.
  • Store indices. Never copy every suffix into its own String.
  • Treat naive sort as the teaching build; switch to a linear construction when n is large.

Don’t:

  • Call indexOf in a loop on a huge, unchanging haystack and call it search.
  • Allocate a suffix tree because the diagram looked more complete.
  • Index a string you will query once, or a buffer that changes every write.
  • Implement SA-IS from a blog post the first time you need O(n) — use a known library.

Wrap-up

A suffix array turns substring search into binary search over sorted suffixes. The text stays put. The index is n integers. You pay to sort (naively O(n² log n), linearly if you outgrow that), then each pattern of length m is O(m log n) plus the hits you collect.

Use it when the haystack is large, stable, and queried often. Use indexOf when you will look once. Use a suffix tree only when you need the extra branching structure, not as the default index. The glossary, the skill path, and the rest of the series live on the Data Structures Roadmap.

Next optional step in the series Recently used keys float to the root. Splay Trees: Move What You Touch