Suffix Arrays and Suffix Automata

Take a string like "banana" and list every suffix — "banana", "anana", "nana", "ana", "na", "a" — then sort those suffixes alphabetically. That sorted list of starting indices is a suffix array, and once you have it, checking whether some pattern occurs anywhere in the string becomes a binary search over the sorted suffixes, since any substring is just a prefix of some suffix. Building the array efficiently (in $O(n \log n)$ or better, rather than the naive $O(n^2 \log n)$ from sorting full strings) relies on ranking suffixes by doubling the compared prefix length at each pass.

A suffix automaton solves a related but distinct problem: it's the smallest possible finite-state machine that accepts exactly the set of all substrings of a string, built incrementally in linear time and linear space, regardless of how many distinct substrings exist (which can be quadratic in the string's length). Where a suffix array is a sorted list you search, a suffix automaton is a compact graph you walk one character at a time, making it well suited to answering "does this pattern occur" or "how many distinct substrings exist" without ever materializing every substring explicitly.

Both structures show up in the same practical spot: matching or counting patterns against a fixed reference string — a genome, a large log file, or in a quant-dev interview, a tickerized string of trade or order-book events — far faster than repeated brute-force scanning.