Suffix Array: Sort Every Suffix, and Substring Search Becomes Binary Search

A suffix array turns a string into an ordered index. The construction is straightforward in principle: write down every suffix of the text, sort those suffixes lexicographically, and store each suffix's original starting position. Once the suffixes are ordered, a substring query can be answered by finding the consecutive range of suffixes that begin with the query pattern.

This article uses one small but complete example:

banana$

The pattern we want to search for is:

ana

The pattern occurs twice, at zero-based positions 1 and 3. The suffix-array method exposes those two occurrences through two binary searches: one search finds the beginning of the matching range, and another finds its end.

The example also records longest common prefix, or LCP, values. An LCP value tells us how many initial characters two neighboring sorted suffixes share. For the two relevant suffixes, ana$ and anana$, the LCP is 3, because both begin with ana.

The important idea is not merely that suffixes are sorted. It is that sorting groups suffixes with the same beginning together. That grouping turns a scattered substring-search problem into an ordered range query.

1. What is a suffix?​

A suffix is a substring that starts at a particular position and continues through the end of the text. If a text has length $n$, it has one suffix beginning at each position from $0$ through $n-1$.

For banana$, the suffixes are:

The suffix beginning at position 0 is the entire text. The suffix beginning at position 1 omits the first character and is anana$. The suffix beginning at position 6 contains only the end marker.

In a real implementation, it is usually unnecessary to copy every suffix into a separate string. The text can be stored once, and a suffix can be represented by its starting position. The table shows complete suffix strings because they make the ordering easy to inspect.

The number of suffixes equals the text length. For this example, the text has seven characters, so there are seven suffixes.

2. Why use the end marker?​

The final $ is a special sentinel, or end marker. It makes the end of every suffix explicit and is considered smaller than the ordinary letters in this example.

Without displaying the marker, the suffixes would look like this:

banana
anana
nana
ana
na
a

With the marker, their boundaries are clear:

banana$
anana$
nana$
ana$
na$
a$
$

The marker is especially useful when one suffix is a prefix of another. Compare a$ with ana$. Both begin with a, but the first suffix ends immediately afterward. Since the end marker sorts before ordinary letters, a$ comes before ana$.

Similarly, ana$ comes before anana$. They share ana, but then the first suffix ends while the second continues with n:

ana$
anana$

The first three characters agree. The next characters are $ and n, so ana$ comes first.

The marker must be handled consistently during sorting and searching. It is part of the comparison model, not an ordinary letter that the query pattern normally contains.

3. Sorting the suffixes lexicographically​

Lexicographic order is dictionary-like order. Compare two strings from left to right. At the first position where they differ, the string with the smaller character comes first. If one string ends after matching the beginning of the other, the shorter string comes first under the sentinel ordering.

Sorting the suffixes of banana$ gives:

The suffix array stores the original positions in this sorted order:

[6, 5, 3, 1, 0, 4, 2]

The entry at rank 2 is 3. That means the third suffix in sorted order begins at original text position 3; it is the suffix ana$.

This distinction between rank and position is fundamental:

• A rank describes where a suffix appears in the sorted index.
• An original position describes where that suffix begins in the text.

The suffix array uses ranks for searching and original positions for reporting results. Sorting changes the order of the index entries, but it does not change the coordinates stored inside them.

4. The sorted order creates prefix groups​

The sorted suffixes are:

rank 0: $
rank 1: a$
rank 2: ana$
rank 3: anana$
rank 4: banana$
rank 5: na$
rank 6: nana$

The suffixes beginning with ana appear at ranks 2 and 3:

ana$
anana$

They are adjacent because all strings beginning with a particular prefix form a contiguous region in lexicographic order. No suffix beginning with b or n can appear between two suffixes beginning with a, and no unrelated suffix beginning with a can be placed between two strings whose next characters keep them inside the ana group.

This property is the basis of substring searching. The occurrences of a pattern do not need to be adjacent in the original text. In banana$, the two occurrences of ana begin at positions 1 and 3, with another character position between them. But their corresponding suffixes are adjacent after sorting.

The suffix array changes the geometry of the problem:

original text:   occurrences may be scattered
sorted suffixes: matching beginnings form one range

Instead of checking every text position independently, a query can locate that range.

5. Why substring search becomes prefix search​

Suppose a pattern $P$ occurs at position $i$ in a text $T$. Then the suffix beginning at $i$ starts with exactly the characters of $P$. In notation, $P$ is a prefix of the suffix $T[i\ldots n-1]$.

For the pattern ana, the first occurrence is:

banana$
 ^^^
 ana

The suffix beginning at position 1 is anana$, whose first three characters are ana.

The second occurrence is:

banana$
   ^^^
   ana

The suffix beginning at position 3 is ana$, which also begins with ana.

Therefore, finding every occurrence of ana is equivalent to finding every suffix whose prefix is ana. Once those suffixes are found in the sorted list, their stored original positions identify the occurrences.

Notice that the suffix does not need to have the same length as the pattern. The pattern matches when it is a prefix:

pattern: ana
suffix:  anana$

The suffix continues after the pattern ends, but that is valid. Likewise, the end marker after ana in ana$ does not prevent a match.

6. The first binary search: find the lower boundary​

A binary search works because the suffixes are sorted. At each step, it compares the pattern with a suffix near the middle of the current rank interval. The result tells the search which half can be discarded.

The first search finds the first suffix that is not smaller than the pattern. In practical terms, this is the first place where suffixes could begin with ana.

The ranks are:

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

Consider the important comparisons.

Comparing with banana$​

The pattern begins with a, while banana$ begins with b:

ana
banana$

Since a comes before b, the pattern belongs before banana$. Suffixes after banana$ also cannot be the first suffix beginning with ana, so the search moves left.

Comparing with a$​

The first character agrees, but a$ ends before the pattern does:

a$
ana

The suffix a$ is smaller than ana, because after the shared a, the suffix reaches the end marker while the pattern continues with n. Therefore, the first matching suffix must be to the right of rank 1.

Comparing with ana$​

All three characters of the pattern match before the suffix reaches its end:

ana
ana$

This suffix begins with the pattern, so it is a valid match and a candidate for the lower boundary.

The resulting division is:

ranks smaller than the pattern:       0 and 1
ranks at or beyond the match range:   2 through 6

The lower boundary is rank 2.

A binary search does not need to inspect every suffix in order. Each comparison eliminates a portion of the sorted rank range. The exact sequence of middle ranks depends on the implementation, but the invariant is the same: all discarded ranks are known to be on the wrong side of the boundary.

7. The second binary search: find the upper boundary​

Finding the first matching rank is not enough when a pattern occurs more than once. The second binary search finds the first rank after the block of suffixes beginning with ana.

The relevant portion of the sorted list is:

rank 1: a$
rank 2: ana$
rank 3: anana$
rank 4: banana$

Ranks 2 and 3 begin with the complete pattern. Rank 4 begins with b, so it lies beyond the matching block. The upper boundary is rank 4, used as an exclusive endpoint.

The two searches therefore identify the half-open interval:

[2, 4)

A half-open interval includes the left endpoint and excludes the right endpoint. Thus it contains ranks 2 and 3:

The suffix-array entries in this range are:

[3, 1]

Those are the original starting positions of the occurrences. If an application wants positions in the order they appear in the text, it reports them numerically as:

[1, 3]

The suffix-array order itself is 3, 1, because ana$ comes before anana$ lexicographically. The text order is 1, 3.

8. Why the matching suffixes are consecutive​

The contiguous-range property follows from lexicographic ordering. Suppose two suffixes begin with ana. Any string that lies between them in sorted order must also lie between two strings with that prefix. It cannot suddenly begin with b or n, because those first characters would place it outside the a group.

For this example:

ana$
anana$

Both strings share the prefix ana, and no unrelated suffix can be placed between them. The matching suffixes form one block even though the original text positions are not consecutive.

This property works for every pattern, including patterns that occur zero times or only once:

• If the two boundaries are equal, the matching interval is empty.
• If the interval contains one rank, the pattern occurs once.
• If the interval contains several ranks, every stored position in the interval is a candidate occurrence.

The suffix array therefore answers both existence queries and reporting queries. To ask whether a pattern occurs, test whether the interval is nonempty. To list all occurrences, enumerate the stored positions in the interval.

9. Longest common prefix values​

LCP means longest common prefix. For two neighboring suffixes in suffix-array order, the LCP value is the number of initial characters they share.

For example, compare ana$ and anana$:

ana$
anana$

They agree on ana, which has length 3. The next characters are $ and n, so the LCP is 3.

For neighboring sorted suffixes in this example, the values are:

If the first suffix has no previous neighbor, its LCP entry is commonly left undefined or represented separately. The remaining LCP list is:

[0, 1, 3, 0, 0, 2]

The LCP value is attached to a boundary between ranks, not directly to an original text position. The value 3 belongs between ranks 2 and 3 because it describes the relationship between the suffixes stored at those ranks.

10. What LCP adds to the index​

The suffix array already gives an ordered search space. LCP values add information about overlap between neighboring suffixes.

The LCP table immediately shows that ranks 2 and 3 share the complete pattern ana:

rank 2: ana$
rank 3: anana$
LCP:      3

It also shows that the suffixes beginning with na share two characters:

na$
nana$

The LCP array is therefore a compact summary of repeated beginnings in sorted order. It avoids repeatedly writing the same shared prefix when examining neighboring suffixes.

For the query ana, the LCP value does not replace the two binary searches. The searches still identify the matching interval. Instead, LCP records help explain the structure of that interval and can support more advanced suffix-array operations in implementations that use them. The factual point demonstrated here is simpler: LCP records how much adjacent sorted suffixes overlap at their beginnings.

A useful way to think about the two data structures is:

• The suffix array answers: “In what order do suffixes appear?”
• The LCP array answers: “How much do neighboring suffixes share?”

Together, they describe both order and local similarity.

11. The complete index for banana$​

Putting the suffix-array entries and LCP values together produces this table:

This table answers several different questions:

• The lexicographically smallest suffix is $, at rank 0.
• The suffix beginning at text position 1 is stored at rank 3.
• The suffix beginning at text position 3 is stored at rank 2.
• The suffixes beginning with ana occupy ranks 2 through 3.
• The shared prefix of the suffixes at ranks 2 and 3 has length 3.
• The occurrences of ana begin at original positions 1 and 3.

The table uses complete suffix strings for clarity. A compact implementation can store the text, the suffix-array positions, and the LCP values without storing seven separate copied strings.

12. A full manual query​

The search for ana can be summarized as a sequence of index operations.

Step 1: Use sorted suffixes​

rank 0: $
rank 1: a$
rank 2: ana$
rank 3: anana$
rank 4: banana$
rank 5: na$
rank 6: nana$

Step 2: Find the lower boundary​

The suffixes at ranks 0 and 1 are smaller than the first possible suffix beginning with ana. Rank 2 is the first matching rank.

lower boundary = 2

Step 3: Find the upper boundary​

Ranks 2 and 3 begin with ana. Rank 4 is the first suffix outside the matching block.

upper boundary = 4

Step 4: Read the suffix-array entries​

suffix-array entries at ranks [2, 4): 3, 1

Step 5: Report positions in text order​

1, 3

The LCP value between ranks 2 and 3 is 3, matching the length of the query pattern.

This is the entire transformation:

text -> sorted suffix positions -> two boundaries -> original positions

13. How this avoids repeated work​

A direct scan for ana could test possible starting positions from left to right. The suffix-array method reorganizes the text before searching. It puts similar suffix beginnings next to each other, so a query can use ordering to eliminate groups of candidates.

Suppose a comparison shows that ana belongs before banana$. There is no need to inspect suffixes beginning with n when locating the lower boundary. Their positions in sorted order already prove that they are too large. A binary-search step discards that entire region rather than checking each suffix individually.

The method does not imply that every character comparison disappears. Comparing a pattern with a suffix may still inspect several characters. The avoided repetition comes from not treating every text position as an unrelated candidate. The sorted index supplies information about whole ranges of suffixes at once.

The LCP values provide a second form of organization. When adjacent suffixes have a large LCP, their initial comparisons overlap. The value 3 between ana$ and anana$ records that their first three characters are already known to agree.

The overall pattern is:

1. Prepare an ordered representation of all suffixes.
2. Group common beginnings through lexicographic order.
3. Use binary search to find the boundaries of a prefix group.
4. Convert the matching ranks back to original text positions.

14. Complexity perspective​

The example explains the representation and search procedure, not one particular suffix-array construction algorithm. Different construction techniques can have different construction-time and space bounds, so no specific construction complexity should be inferred from this example alone.

If the text has length $n$, the suffix array contains $n$ entries. The LCP record has one value for each adjacent pair of sorted suffixes, so it contains $n-1$ values when the first suffix has no preceding neighbor.

The boundary searches have the structure of binary search over $n$ sorted ranks. They make $O(\log n)$ rank decisions per boundary. There are two boundaries, so the number of boundary decisions remains logarithmic up to a constant factor.

Each decision compares the pattern with a suffix. If the pattern has length $m$, the actual character-comparison cost depends on how many characters are examined during those comparisons and on the comparison implementation. Thus it is more precise to say that the rank search is logarithmic in the number of suffixes, while the total character work also depends on the pattern and comparison behavior.

If the query matches $k$ suffixes, reporting their stored original positions takes work proportional to $k$ after the matching interval has been located. A result-producing query therefore has a boundary-finding component plus an output component.

The main trade-off is preparation versus repeated queries. The text must be organized into a suffix array before these searches can use it. In return, subsequent substring searches work with a sorted index rather than repeatedly starting from an unsorted set of text positions.

15. Ranks and original positions are different​

A common mistake is to confuse a suffix's rank with its text position. The suffix array is:

[6, 5, 3, 1, 0, 4, 2]

The entry at rank 2 is 3, not 2. Rank 2 means “the suffix is third in sorted order.” The value 3 means “the suffix begins at position 3 in the original text.”

For the pattern ana, the matching entries are:

rank 2 -> text position 3
rank 3 -> text position 1

The suffix-array order of the matches is therefore 3, 1. If the application wants locations in the order they occur in the text, it can sort or otherwise return them as 1, 3.

Different applications may want different output orders. A program checking only whether a match exists needs only to know whether the interval is empty. A program listing suffix-array matches can return them in rank order. A program displaying occurrences in document order may need to arrange the original positions numerically.

The index's job is to identify the correct original coordinates. The desired presentation order is a separate decision.

16. Boundary cases​

The same two-boundary idea handles several useful cases.

No occurrence​

If the lower and upper boundaries are equal, no suffix begins with the pattern. The matching interval is empty.

One occurrence​

If the upper boundary is exactly one rank after the lower boundary, the interval contains one suffix and therefore one occurrence position.

Several occurrences​

If the interval contains several ranks, every corresponding suffix begins with the pattern. The suffix-array entries in the interval provide all occurrence positions.

Pattern longer than a suffix​

A suffix such as a$ cannot match ana, because the suffix ends before all pattern characters have matched. The end marker makes that comparison explicit: after a, the suffix has ended while the pattern still requires n.

Pattern equal to a suffix prefix​

The pattern ana does match both ana$ and anana$. A match requires the pattern to be a prefix of the suffix, not an exact full-string equality.

These cases are why the comparison rules and the two boundary definitions must be consistent. Sorting and searching must agree about the end marker, shared prefixes, and the difference between a prefix match and an exact suffix match.

17. Practical uses of suffix-array indexing​

A suffix array is useful when the same text will be searched repeatedly. The index is prepared once, and later substring queries can locate matching suffix ranges through the sorted order.

For a document represented as one text, a query follows the same conceptual workflow as the example:

text -> suffixes -> sorted suffix order -> two boundary searches -> positions

The example is intentionally small, but the structure scales conceptually to longer text. The important practical lesson is not a particular user-interface design or construction method. It is that sorted suffixes provide an index for repeated substring queries, while LCP values record shared beginnings among neighboring entries.

The idea also has a useful connection to autocomplete, although the structures are not identical. An autocomplete index commonly groups terms by their beginnings. A suffix array groups every suffix of a text by lexicographic order. In both cases, a prefix identifies a contiguous region in an ordered structure. Here, the prefix is the search pattern, and the region contains suffixes that begin with that pattern.

For a search box over a fixed body of text, the suffix-array viewpoint explains how a query can be mapped to a range of indexed locations. The stored positions then identify where the query occurs. Whether an application displays those positions, counts them, or uses them for another operation is outside the small example, but the index provides the locations.

18. Implementation details worth preserving​

A correct implementation must keep several relationships synchronized.

First, every text position must produce exactly one suffix. For banana$, positions 0 through 6 produce seven suffixes.

Second, the sorting operation must compare suffix contents, not numerical starting positions. Numerical position order would be:

[0, 1, 2, 3, 4, 5, 6]

That is not the suffix-array order. The correct lexicographic order is:

[6, 5, 3, 1, 0, 4, 2]

Third, the end marker must have a defined ordering rule. It allows shorter suffixes to be compared cleanly with longer suffixes that share their beginning.

Fourth, binary-search comparisons must follow the same ordering rules used during suffix sorting. If sorting treats the marker as smaller than ordinary characters but searching handles it differently, the computed boundaries may be incorrect.

Finally, LCP values must be associated with neighboring ranks. The LCP value 3 is not a property of text position 3 alone or text position 1 alone. It describes the boundary between the suffix at rank 2 and the suffix at rank 3.

19. Final takeaway​

For the text banana$, the suffixes are:

banana$
anana$
nana$
ana$
na$
a$
$

After sorting them, the suffix array is:

[6, 5, 3, 1, 0, 4, 2]

The suffixes beginning with ana are:

ana$
anana$

They occupy the consecutive rank interval [2, 4). Two binary searches find the lower boundary 2 and the exclusive upper boundary 4. The suffix-array entries in that interval are original text positions 3 and 1, which correspond to the two occurrences of ana at positions 1 and 3 when reported in text order.

The LCP values add a compact description of neighboring overlap. In particular, the LCP between ana$ and anana$ is 3, because their shared prefix is ana.

The essential process is:

sort every suffix
store its original position
record neighboring LCP values
binary-search the first matching rank
binary-search the end of the matching range
report the stored text positions

A suffix array does not remove the text or make comparisons unnecessary. It reorganizes the text so that suffixes with similar beginnings become neighbors. That organization is the valuable part: a substring query becomes a search for the boundaries of one ordered range, and the range's stored positions reveal every occurrence.