Suffix Array: Indexing Every Ending of a String

What Exactly Is a Suffix?

A suffix of a string is everything from some starting position through to the end of the string. If the string is banana, it has exactly six suffixes, one beginning at each index: banana, anana, nana, ana, na, and a. Notice that the full string itself counts as a suffix too, the one that starts at position zero. In general, a string of length n has exactly n suffixes, one for every possible starting index, including the empty suffix if you choose to count it, though most implementations stop just before that. This is different from a prefix, which is everything from the beginning of the string up to some cutoff point, and different again from an arbitrary substring, which can start and end anywhere in the middle. The key insight that makes suffixes so useful is this: any substring of the original text is a prefix of exactly one suffix, namely the suffix that starts where the substring starts. So if you want to know whether the pattern ana occurs inside banana, you are really asking whether ana is a prefix of any of banana's six suffixes. Looking at the list above, ana is indeed a prefix of the suffix ana itself, and also a prefix of anana. This reframing is the whole trick behind the suffix array: instead of searching the raw text for a pattern, you organize all suffixes so that finding a pattern becomes finding a range of suffixes that share it as a prefix. It is worth emphasizing that this technique concerns one string and its own internal echoes, its repeated fragments, its symmetric patterns, not a collection of many different words the way a dictionary trie would be organized.

Building the Array: The Naive Way

The most straightforward way to build a suffix array is refreshingly direct. First, generate all n suffixes of the string. Second, sort them using ordinary alphabetical, or lexicographic, comparison. Third, record only the starting index of each suffix in that sorted order, discarding the actual suffix text since it can always be recovered from the original string plus the index. For banana, sorting the six suffixes alphabetically gives: a, ana, anana, banana, na, nana, which correspond to starting positions 5, 3, 1, 0, 4, 2. That sequence of positions, 5, 3, 1, 0, 4, 2, is the suffix array. The problem with this approach is efficiency. Comparing two suffixes character by character can take time proportional to the length of the string in the worst case, since two suffixes might share a very long common beginning before differing. With n suffixes to sort and a general-purpose comparison sort needing on the order of n log n comparisons, and each comparison costing up to n character checks, the total work lands at order n squared log n in the worst case. For a short word like banana this is instantaneous, but for a human chromosome with hundreds of millions of bases, or a large corpus of documents, order n squared log n becomes completely impractical, potentially requiring longer than the age of the universe to finish. This naive method is valuable for building intuition and for small-scale examples, but any real-world deployment, especially in genome sequencing pipelines that must index entire chromosomes, needs a fundamentally faster construction strategy.

Building the Array Efficiently: Prefix Doubling and Skew

Faster suffix array construction algorithms avoid comparing suffixes character by character from scratch every time. The most widely taught approach is called prefix doubling. It works in rounds. In the first round, every suffix is ranked based on just its first character, using the ordinary alphabet order, so identical first characters receive the same rank. In the second round, each suffix is ranked using a pair of ranks: its own current rank plus the current rank of the suffix starting two characters later, which together summarize the first two characters efficiently. In the next round, the comparison window doubles again to four characters, then eight, then sixteen, and so on, always reusing the ranks computed in the previous round rather than rereading raw text. Because the window doubles each round, only about log n rounds are needed before every suffix has a unique rank, and each round can be completed in order n log n time using an efficient sort, giving a total construction time of order n log n multiplied by log n, which is already a dramatic improvement over the naive method, and can be tightened further with radix sorting tricks. An even faster family of algorithms, most famously the DC3 algorithm, also called the skew algorithm, achieves true order n time. Conceptually, DC3 splits the suffixes into groups based on their starting position modulo three, recursively sorts one manageable group using a clever reduction to a smaller version of the same problem, then merges in the remaining suffixes using the results from that recursive step. The details are intricate, but the payoff is that even suffix arrays for entire genomes or massive text corpora can be constructed in time roughly proportional to the size of the input, which is why these algorithms underpin real bioinformatics and search infrastructure.

Searching with Binary Search

Once the suffix array is built and sorted, searching for a pattern of length m inside a text of length n becomes remarkably fast. Because the suffixes are arranged in alphabetical order, all suffixes that begin with a given pattern sit together in one contiguous block of the array, exactly the same way all dictionary words starting with cat sit together on a dictionary page. This means you can use binary search, repeatedly checking the middle suffix of a shrinking range and comparing the pattern against its first m characters, to home in on that block. Each comparison during the binary search costs at most order m character checks, since you only ever need to look at the first m characters of the candidate suffix to see whether the pattern matches as a prefix. Binary search itself needs about log n comparisons to narrow down from n candidates to the target range. Multiplying these together gives a total search time of order m log n, which barely depends on the size of the surrounding text at all, only on the length of the pattern being searched for and the logarithm of the text length. Two binary searches, one to find the leftmost matching suffix and one to find the rightmost, reveal not just whether the pattern exists but exactly how many times it occurs and at which positions, since every suffix in that matched block corresponds to one occurrence. This is an enormous improvement over scanning the raw text directly, which in the worst case takes time proportional to the full length of the text multiplied by the pattern length. For searching a short DNA fragment against an entire chromosome, or a search-engine query against a huge indexed document, that difference determines whether the search finishes instantly or takes an impractically long time.

The LCP Array, Suffix Trees, and Tries

The suffix array pairs beautifully with a companion structure called the LCP array, short for longest common prefix. Each entry in the LCP array records how many leading characters two neighboring suffixes in the sorted order share. This extra information speeds up searches further, since a binary search can skip redundant character comparisons it has effectively already made, and it directly answers other questions too. The longest value anywhere in the LCP array immediately reveals the longest repeated substring within the text, the longest fragment that appears more than once. Concatenating two strings together with a unique separator character and then examining the LCP array of the combined string reveals the longest common substring shared between the two original strings, a technique used in plagiarism detection and DNA comparison between species. It is natural to ask how this compares with related structures. A suffix tree stores the same suffix information but as an explicit branching tree, where shared prefixes are collapsed into shared paths from the root; it answers many of the same queries and some more advanced ones just as quickly, but its pointers and internal nodes typically consume noticeably more memory than the plain arrays of integers a suffix array and LCP array require. This is a genuinely useful trade-off: suffix arrays sacrifice a little query flexibility and construction elegance for a smaller memory footprint, which matters enormously when indexing genomes with billions of bases. It is also worth clearly separating this from a trie, which this site covers elsewhere: a trie is typically built from many separate words or keys to support prefix lookup across that whole collection, whereas a suffix array is built from all the suffixes of one single string, revealing the internal repeated structure within that one piece of text rather than relationships across many different entries.

Frequently asked questions

Try it live

Everything above runs in your browser — open Suffix Array: Indexing Every Ending of a String and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.