cf.completefrontend
STRING ALGORITHMS · ADVANCED

Suffix array

List the start positions of all suffixes of a string in sorted order, so repeated pieces end up next to each other.

Time O(n log^2 n)Space O(n)4 practice problemsStep-through picture

The idea

A suffix is a piece of a string that runs to its end. banana has six: banana, anana, nana, ana, na, and a. A suffix array lists their start positions in alphabetical order of the suffixes. For banana that is [5, 3, 1, 0, 4, 2], for a, ana, anana, banana, na, nana.

Why sort suffixes? Every substring is the start of some suffix. After sorting, suffixes that start the same way sit next to each other, like words in a dictionary. So repeated substrings, the number of different substrings, and pattern search all become questions about neighbors in one sorted list.

Sorting the suffixes by comparing them as strings can be slow, because each comparison may read the whole string. The prefix doubling method sorts by the first 1 character, then the first 2, then 4, 8, and so on. Each round uses the ranks from the round before, so comparing two suffixes is just comparing two pairs of numbers.

An everyday example

Sorting library cards a little at a time

You must put cards in dictionary order but you can only see a few letters at a time. First you group cards by their first letter and number the groups. Next you look at the first two letters. You don't read them again: each card's two letters are its own group number and the group number of the card that starts one letter later. Then you use those numbers to sort by four letters, then eight. Each round doubles what you know, until every card has its own number.

How the example maps to the code
In the exampleIn the code
A cardA suffix, named by its start index
The group number from the last roundrank[i]
The group number of the card one step furthersecond(i), which is rank[i + k]
The cards in current orderorder
Every card has its own numberrank[order[n - 1]] === n - 1

From the slow way to suffix array

  1. The obvious way builds every suffix with slice and sorts them as strings. The copies take O(n^2) memory, and each comparison can read up to n letters, so the sort costs up to O(n^2 log n). For a text of 100,000 letters, that's far too much.
  2. Comparing whole suffixes repeats work: every comparison re-reads letters that other comparisons already read. What if each suffix had a small number, a rank, saying where its first few letters sort? Then comparing two suffixes by those letters takes one number comparison.
  3. Ranks by the first k letters give ranks by the first 2k letters with little extra work. The first 2k letters of the suffix at i are its first k letters followed by the first k letters of the suffix at i + k. So the pair rank[i], rank[i + k] sorts suffixes by 2k letters. A suffix too short for a second half gets -1, so it sorts first.
  4. Start with ranks by one letter: the character codes. Sort by pairs, give equal pairs equal new ranks, and double k. Once every rank is different, the order can't change any more, so stop. Rank, pair, sort, re-rank, double: that loop is a suffix array by prefix doubling.

How it works

  1. Start order as [0, 1, ..., n - 1] and rank[i] as the character code of text[i]. This ranks suffixes by their first character.
  2. For k = 1, 2, 4, ..., a suffix starting at i is described by the pair rank[i] and second(i) = rank[i + k], or -1 if i + k is past the end.
  3. Sort order by these pairs. Now suffixes are ordered by their first 2k characters.
  4. Give new ranks: walk order; each suffix gets the previous one's rank, plus one if its pair differs.
  5. If the last suffix in order has rank n - 1, every rank is different and the order is final. Otherwise double k and repeat.
  6. The final order is the suffix array.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function suffixArray(text) {
  2. const n = text.length;
  3. const order = Array.from({ length: n }, (_, i) => i);
  4. let rank = order.map((i) => text.charCodeAt(i));
  5. for (let k = 1; n > 1; k *= 2) {
  6. const second = (i) => (i + k < n ? rank[i + k] : -1);
  7. const compare = (a, b) => rank[a] - rank[b] || second(a) - second(b);
  8. order.sort(compare);
  9. const next = new Array(n).fill(0);
  10. for (let p = 1; p < n; p++) {
  11. const isNew = compare(order[p - 1], order[p]) !== 0;
  12. next[order[p]] = next[order[p - 1]] + (isNew ? 1 : 0);
  13. }
  14. rank = next;
  15. if (rank[order[n - 1]] === n - 1) break;
  16. }
  17. return order;
  18. }

How fast it is

TimeO(n log^2 n)
Extra memoryO(n)

There are about log n doubling rounds and each one sorts n positions with O(1) comparisons. The arrays order, rank, and next each hold n numbers.

  • Best caseO(n log n)

    All letters are different, like zyxwv: the first round already gives every suffix its own rank, so one sort finishes the job.

  • Average caseO(n log^2 n)

    Ordinary text: a few doubling rounds, each one a sort with O(1) comparisons.

  • Worst caseO(n log^2 n)

    One letter repeated, like aaaaaaaa: ties last until 2k reaches n, so about log₂ n rounds are needed, each costing O(n log n).

Common mistakes

  • Sorting the suffix strings themselves with slice and localeCompare. It is correct but can take O(n^2 log n) time and O(n^2) memory.
  • Giving a suffix that runs out the rank 0 instead of -1. It then ties with a real character's rank and sorts in the wrong place.
  • Updating rank while still computing new ranks. Build the new ranks in a separate array next, then replace rank.
  • Forgetting the stopping test and always running log n rounds. That is still correct but wastes rounds on text that is already fully ranked.

When to use it

Look for these clues in a problem:

  • The question asks about repeated substrings, such as the longest one that appears twice.
  • You need the number of different substrings of a string.
  • You will search one long text for many different patterns.
  • The question is about the alphabetical order of suffixes or rotations of a string.

Check yourself

Answer each one in your head first, then open it.

Why does a missing second half get -1 and not 0?

Real ranks start at 0, so 0 would tie with a real letter. A suffix that ends early must sort before every longer suffix with the same start, and -1 is smaller than every rank.

Why are the new ranks written to next instead of straight into rank?

The compare function reads rank while the new ranks are computed. Changing rank in place would mix old and new values in the same round.

At most how many rounds does a text of 1,000 letters need?

About 10, because k doubles each round and 2^10 is 1,024. After that, every suffix's whole length has been compared.

What is the suffix array of "aaaa", and why?

[3, 2, 1, 0]. Every suffix is a run of a, so the shorter one sorts first, just like a before aa in a dictionary.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule after each round with step k: order lists the suffixes sorted by their first 2k letters, and rank[i] is the position of the suffix at i in that sorted list, with equal ranks for equal first 2k letters. A suffix shorter than 2k letters counts as ending early, which sorts before any letter.

Each round keeps the rule. The first 2k letters of the suffix at i are its first k letters, already ranked by rank[i], followed by the next k letters, ranked by rank[i + k], or nothing at all, ranked -1. Comparing pairs therefore compares the first 2k letters exactly. Walking the sorted order and adding one each time the pair changes gives equal ranks to equal pairs and bigger ranks to bigger pairs. The new ranks go in a separate array, next, so the round reads only old ranks.

When the largest rank is n - 1, all n ranks are different, so no two suffixes tie on their first 2k letters, and longer prefixes can't change their order. The loop stops after at most about log₂ n rounds, because 2k reaches n by then and suffixes of different lengths can't tie on all of their letters.

Going deeper

3 more ideas

Why the pair of ranks is enough

The first 2k characters of the suffix at i are its first k characters followed by the first k characters of the suffix at i + k. The previous round already ranked every suffix by its first k characters. So comparing the pairs (rank[i], rank[i + k]) compares the first 2k characters, without reading any text.

How fast it is

Each round doubles k, so there are at most about log n rounds. Each round sorts n items with a comparison that costs O(1), which is O(n log n). In total that is O(n log^2 n). Faster methods exist, such as counting sort in each round for O(n log n), or linear-time algorithms, but they are longer to write.

The LCP array

The suffix array is often paired with an LCP array: for each pair of neighbors in sorted order, the length of their longest common prefix. Kasai's algorithm builds it in O(n). The largest LCP value is the length of the longest repeated substring, and n * (n + 1) / 2 minus the sum of all LCP values is the number of different substrings.

Work it by hand

Every step in a table, with why

Sort the 6 suffixes of a word with three a letters. Two rounds are needed, because after the first round two suffixes still tie.

text = "papaya"

StepkSteporderrank (by position)What happensWhy
1-start[0, 1, 2, 3, 4, 5][112, 97, 112, 97, 121, 97]rank by first letterrank[i] is the character code of text[i]: p is 112, a is 97, and y is 121.
21pairs[0, 1, 2, 3, 4, 5][112, 97, 112, 97, 121, 97]pair with rank[i + 1]The pairs are (112, 97), (97, 112), (112, 97), (97, 121), (121, 97), and (97, -1) for the last suffix, a, which has no second letter.
31sort[5, 1, 3, 0, 2, 4][112, 97, 112, 97, 121, 97]order by 2 lettersBy their first 2 letters: a, ap, ay, pa, pa, ya. Suffixes 0 and 2 both start with pa.
41re-rank[5, 1, 3, 0, 2, 4][3, 1, 3, 2, 4, 0]last rank is 4, not 5Walking order, each pair that differs from the one before gets the next rank. Suffixes 0 and 2 share rank 3, so the order isn't final yet.
52pairs[5, 1, 3, 0, 2, 4][3, 1, 3, 2, 4, 0]pair with rank[i + 2]Now second(i) looks 2 places ahead. Suffix 0 gets (3, 3) and suffix 2 gets (3, 4), because pa is followed by pa in one and by ya in the other.
62sort[5, 1, 3, 0, 2, 4][3, 1, 3, 2, 4, 0]order by 4 letters(3, 3) comes before (3, 4), so suffix 0, papa, stays before suffix 2, paya. The order happens not to change.
72re-rank[5, 1, 3, 0, 2, 4][3, 1, 4, 2, 5, 0]last rank is 5: stopAll six ranks are different now, so rank[order[5]] === 5 and the loop breaks.

It returns [5, 1, 3, 0, 2, 4], the starts of a, apaya, aya, papaya, paya, and ya. Two rounds were enough, while aaaaaa, of the same length, needs 3, because its ties last longer.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Suffix arrayO(n log^2 n)O(n)Many questions about one text: repeated pieces, different substrings, or many pattern searches.
Counting-sort doublingO(n log n)O(n)The same result faster for large texts, with a little more code.
Sort sliced suffixesO(n^2 log n)O(n^2)Only for short texts or to test the fast version.
KMP pattern searchO(n + m)O(m)You only need to find one pattern once; building a suffix array isn't worth it.

Extra memory: O(n): the arrays order, rank, and next each hold n numbers. No suffix is ever copied as a string.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Suffix array and the other approaches, on a scale where each line up is 10 times more steps.
  • Suffix array O(n log^2 n)
  • Counting-sort doubling O(n log n)
  • Sort sliced suffixes O(n^2 log n)
  • KMP pattern search O(n + m)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Suffix array11099,317397 million
Counting-sort doubling339,96620 million
Sort sliced suffixes33210 million20 trillion
KMP pattern search202,0002 million

Inputs that need care

5 tricky inputs
Empty text: ""
order is [], and n > 1 is false, so the loop never runs. It returns [].
One letter: "z"
n > 1 is false, so it returns [0] without sorting.
All the same letter: "aaaa"
It takes two rounds and returns [3, 2, 1, 0]: shorter suffixes come first, because the -1 for a missing second half sorts before every real rank.
Upper- and lowercase letters: "bA"
Ranks start from character codes, and every capital letter's code is smaller than every lowercase one's. So it returns [1, 0]: A sorts before bA. Lowercase a copy first if case shouldn't matter.
A long text, like 100,000 letters
About 17 rounds at most, since 2^17 passes 100,000, each sorting 100,000 numbers. That runs in well under a second, while slicing all suffixes would use about 5 billion characters of memory.

Variations and follow-ups

Twists interviewers add

The LCP array

For each pair of neighbors in order, store the length of their longest common prefix. Kasai's algorithm builds it in O(n) from the suffix array. The largest value is the length of the longest repeated substring.

Pattern search

Every occurrence of a pattern is the start of some suffix, and those suffixes sit next to each other in order. Binary search order for the first and last suffix that starts with the pattern, comparing up to m letters each time: O(m log n) per search.

Counting sort in each round

Ranks are whole numbers below n, so each round can sort the pairs with two passes of counting sort instead of a comparison sort. That makes each round O(n) and the whole build O(n log n).

Number of different substrings

Each suffix starts n - order[p] substrings, but the first lcp[p] of them already appeared at the previous suffix. Adding n - order[p] - lcp[p] over all positions counts every different substring once.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "longest repeated substring", "number of distinct substrings", or "many pattern searches in one fixed text". Sorting suffixes puts similar pieces next to each other.
  • Explain the doubling with one sentence: "ranks by the first k letters give ranks by 2k letters, because the first 2k letters are two blocks of k". Then mention the -1 for missing second halves.
  • Say the cost of each version honestly: O(n log^2 n) with a normal sort, O(n log n) with counting sort. In an interview, the simple version is usually enough.
  • Test by hand: one letter, all the same letter, and a short word with ties, like papaya. The usual follow-up is the LCP array, which turns "longest repeated substring" into "largest neighbor value".

Where frontend code uses it

The same idea in real UI code
  • Substring search indexes, where a query may match anywhere inside a word, are often built on suffix arrays: every match of a query is a block of neighboring suffixes that binary search finds quickly.
  • Compression tools use sorted suffixes or rotations: bzip2 is based on the Burrows-Wheeler transform, which sorts all rotations of the input.
  • Finding the longest piece of code or text that appears twice, such as duplicated blocks across bundles, is a classic suffix array question.

Related algorithms