Lesson · Strings and Pattern Matching · Many patterns, and the text itself

The Suffix Array, and What a Sorted Order Answers

The suffix array of banana is 5, 3, 1, 0, 4, 2 and prefix doubling reaches it in two rounds. Beside it the LCP array — 0, 1, 3, 0, 0, 2 — turns the order into answers: its largest entry is the longest repeated substring, ana, and subtracting its sum from 21 gives the exact number of distinct substrings, 15. Both arrays are checked against the definitions, which are quadratic and obvious.

Open the interactive lesson Practice

banana: sa = 5, 3, 1, 0, 4, 2 a, ana, anana, banana, na, nana prefix doubling: sort by 1 character, then use those ranks to sort by 2, 4, 8 two rounds on six characters, 21 comparisons, checked against sorting the strings lcp = 0, 1, 3, 0, 0, 2 overlap with the suffix one rank above longest repeated substring = the largest LCP entry = ana, of length 3 distinct substrings = n(n + 1)/2 − sum of lcp = 21 − 6 = 15

One sorted order, and the two questions it answers exactly

Core ideas

What this lesson establishes

The hard idea is that sorted order puts every repeat next to itself. The other two are prefix doubling and the counting identity.

Sorting the suffixes puts every repeated substring beside itself

A substring that occurs twice is a common prefix of two suffixes, and in sorted order those two suffixes are adjacent or separated only by suffixes that also share that prefix. So the longest repeated substring is the largest overlap between two NEIGHBOURS in the sorted order, and nothing further apart needs checking. On banana the neighbours ana and anana share ana, which is the answer, and it sits in the LCP array as its largest entry.

Prefix doubling sorts by ranks rather than by strings

Round one sorts the starting positions by their first character. Round r then sorts by the pair of ranks from round r − 1 at distance 2^(r−1), which orders the suffixes correctly to 2^r characters while comparing two small integers rather than two strings. The order is correct once every rank is distinct, so log2 n rounds suffice: banana needs 2, mississippi needs 3. The panel prints each round's order and checks the final answer against sorting the suffixes as whole strings, which is the definition and is quadratic.

The LCP array makes the order answer questions, exactly

There are n(n + 1)/2 substrings counted with repeats — 21 for a text of 6. Each LCP entry counts the prefixes this suffix shares with the one above, and those contribute no new substring, so the distinct count is n(n + 1)/2 minus the sum of the LCP array: 21 − 6 = 15 on banana. The two extremes are worth holding: abcdefgh has every LCP zero and all 36 of its substrings distinct, and aaaaaaaa has LCP sum 28 and only 8.

The material

Every suffix in order, and the two arrays that follow

The definitions, the doubling construction, the theorem that makes neighbours enough, and the counting identity.

Definition · Suffix array and LCP array

For a text s of length n, the suffix array sa is the permutation of 0, 1, ..., n − 1 that lists the starting positions of the suffixes of s in increasing lexicographic order of the suffixes. The LCP array has lcp[0] = 0 and, for r ≥ 1, lcp[r] equal to the length of the longest common prefix of the suffixes at ranks r − 1 and r.

Example · The six suffixes of banana

In lexicographic order they are a, ana, anana, banana, na and nana, starting at 5, 3, 1, 0, 4 and 2. So sa is 5, 3, 1, 0, 4, 2. The overlaps between consecutive pairs are 0, then a between a and ana, then ana between ana and anana, then 0 between anana and banana, then 0 between banana and na, then na between na and nana. So lcp is 0, 1, 3, 0, 0, 2.

Theorem · The longest repeated substring is the largest LCP entry

A string w occurs at two or more distinct positions of s if and only if some entry of the LCP array is at least the length of w. Consequently the longest repeated substring of s has length equal to the maximum entry of the LCP array.

Suppose w occurs at positions i and j with i not equal to j. Then w is a prefix of both the suffix at i and the suffix at j. Every suffix lying between them in sorted order also has w as a prefix, because lexicographic order places all strings beginning with w contiguously. So two ADJACENT suffixes in that block share w, and their LCP entry is at least the length of w.

Conversely if lcp[r] is at least the length of w and w is the prefix of that length, then w prefixes the suffixes at ranks r − 1 and r, which start at two distinct positions, so w occurs twice.

Taking w as long as possible in each direction gives the equality of lengths. On banana the maximum entry is 3, at rank 2, and the substring is ana.

□

The force of that theorem is the word ADJACENT. Without it, finding the longest repeat would mean comparing every pair of suffixes; with it, n − 1 neighbour comparisons suffice, and the LCP array has already done them.

Theorem · The number of distinct substrings

The number of distinct non-empty substrings of s is n(n + 1)/2 minus the sum of the LCP array.

Count by the rank of the suffix each substring is first attributed to. The suffix at rank r, starting at sa[r], has n − sa[r] non-empty prefixes, and each substring of s is a prefix of at least one suffix.

Attribute a substring to the LOWEST rank whose suffix has it as a prefix. The prefixes of the rank-r suffix already attributed to an earlier rank are exactly its prefixes shared with the rank-r − 1 suffix, of which there are lcp[r], because sorted order makes the previous suffix the one sharing most with it.

So rank r contributes n − sa[r] − lcp[r] new substrings. Summing over r gives sum(n − sa[r]) − sum(lcp[r]), and the first sum is n^2 − (0 + 1 + ... + n − 1) = n(n + 1)/2.

□

On banana that is 1 + 2 + 2 + 6 + 2 + 2 = 15, and 21 − 6 = 15 as well. The panel prints both routes and they are the same integer, which is the check that the identity was used rather than believed.

Two doubling rounds, watched

Round one sorts the six positions by their first character, giving 5, 1, 3, 0, 2, 4 — the three positions starting a first, then b, then the two starting n, each group in whatever order the ranks left them. Round two sorts by pairs of round-one ranks at distance 1, which is enough to separate every suffix, and produces 5, 3, 1, 0, 4, 2. Two rounds, 21 comparisons, and the result agrees with sorting the six suffixes as whole strings.

text n rounds comparisons longest repeat distinct / all banana 6 2 21 ana (3) 15 / 21 mississippi 11 3 66 issi (4) 53 / 66 abracadabra 11 3 70 abra (4) 54 / 66 abcdefgh 8 1 7 none (0) 36 / 36 aaaaaaaa 8 3 37 aaaaaaa (7) 8 / 36

The last two rows are the extremes of the counting identity. With every character distinct the LCP array is all zeros and every one of the 36 substrings is distinct; with one character repeated the LCP array is the staircase 0, 1, 2, ..., 7 summing to 28, and 36 − 28 = 8, which is n — the only distinct substrings are the runs of length 1 to 8.

The round column is the one to read against a bound. log2 n is about 2.6 for banana and about 3.5 for mississippi, and the measured rounds are 2 and 3: the construction stops as soon as every rank is distinct, which can be sooner than the ceiling. abcdefgh needs one round, because a single character already separates all eight suffixes.

What is checked against what

The suffix array is checked against sorting the suffixes as whole strings with string comparison, which is the definition and costs O(n^2 log n). The LCP array is checked against comparing each adjacent pair character by character, which is the definition and costs O(n^2). The fast constructions — prefix doubling and Kasai's one pass — are the ones whose correctness is not obvious, and they are the ones being checked.

Kasai's pass deserves the scrutiny in particular, because its whole idea is that the LCP of a suffix can be computed from the LCP of the suffix one position earlier in the TEXT, which loses at most one character. That is an argument about a quantity carried between iterations, and a carried quantity is the shape of error that no later step corrects — the same reason the rolling hash on an earlier page is recomputed from scratch.

Interactive

The suffix array, and the questions a sorted order answers

Prefix doubling against sorting the suffixes, and the LCP array against comparing them

Type a text and sort every suffix of it

The upper table is one row per doubling round, showing the order and the rank of each starting position; the lower one is the finished suffix array with the same array produced by sorting the suffixes as whole strings beside it. The bar chart is the LCP array, and its tallest bar is the longest repeated substring.

Worked example

The text

Highlight rank1

Length n—

Doubling rounds—

Comparisons, prefix doubling—

The suffix array agrees with sorting—

The LCP array agrees with comparing—

Longest repeated substring—

Distinct substrings—

All substrings, with repeats—

Prefix doubling sorts the suffixes by their first character, then uses the ranks from that round to sort by 2, 4, 8 characters at a time — so each round compares PAIRS OF RANKS rather than strings, and there are log2 n of them. The answer is checked against sorting the suffixes as whole strings, which is the definition and is quadratic. The LCP array then makes the sorted order answer questions: the longest repeated substring is its largest entry, and the number of distinct substrings is n(n + 1)/2 minus the sum of it.

Method

Sorting the suffixes, then reading the answers off

Write the suffixes out and sort them by hand once. Everything after that is arithmetic on two arrays.

List the suffixes and sort them as strings

For a six-character text that is six strings and takes a minute. Doing it once is what makes the doubling construction recognisable as a faster route to the same array rather than a different object.

Fill the LCP array by comparing neighbours only

Compare each suffix with the one above it, character by character, and stop at the first difference. The theorem is what licenses looking at neighbours and nothing else.

Read the longest repeat off the largest entry

The value is the length and the position is the rank, so the substring is the first few characters of the suffix at that rank. On banana that is rank 2, length 3, and the suffix anana — giving ana.

Count distinct substrings two ways and require the same integer

n(n + 1)/2 minus the LCP sum, and the per-rank sum of n − sa[r] − lcp[r]. They must agree; if they do not, the LCP array is wrong somewhere and the first route would not have revealed it.

Order, overlap, and what they answer

Score 0 / 0

Choose the answer you can justify.

Banana, sorted by hand and then counted

The text is banana, six characters, positions 0 to 5. The six suffixes are written out, sorted as strings, and then the LCP array is filled by comparing each with the one above it.

rank starts at suffix lcp with the one above shared 1 5 a 0 - 2 3 ana 1 a 3 1 anana 3 ana 4 0 banana 0 - 5 4 na 0 - 6 2 nana 2 na sa 5 3 1 0 4 2 by sorting the strings 5 3 1 0 4 2 agree lcp 0 1 3 0 0 2 sum = 6 doubling round 1 (k = 1) 5 1 3 0 2 4 doubling round 2 (k = 2) 5 3 1 0 4 2 done comparisons 21 longest repeat largest lcp entry, 3, at rank 3 = ana all substrings n(n + 1)/2 = 6 x 7 / 2 = 21 distinct 21 - 6 = 15 check, per rank 1 + 2 + 2 + 6 + 2 + 2 = 15

Look at ranks 2 and 3. They are the two suffixes beginning ana, they are adjacent, and their overlap is 3 — so ana occurs twice, at positions 3 and 1. That adjacency is not luck: sorted order puts every string beginning with ana together, so any repeat has to show up between neighbours, which is exactly what the theorem says and why n − 1 comparisons are enough.

For a faded rehearsal, do abab the same way. The supplied first move: the four suffixes are ab, abab, b, bab, so sa is 2, 0, 3, 1. Fill the LCP array, give the longest repeat, and give the distinct count both ways — n(n + 1)/2 is 10 here.

Then predict, without writing anything out, the LCP array and the distinct count for a text of eight identical characters. The supplied hint is that the sorted order is the suffixes in decreasing length. Say what the LCP sum is and why the distinct count comes out at exactly n.

Common mistakes

Looking for a repeat between non-adjacent suffixesIt cannot help and it costs n^2 comparisons. If two suffixes far apart in the order share a prefix w, every suffix between them shares it too, so an adjacent pair inside that block shares at least as much. The LCP array over neighbours is complete evidence, and that is what the theorem establishes.

Subtracting the LCP sum from n^2 rather than from n(n + 1)/2The number of substrings counted with repeats is n(n + 1)/2, which is 21 for a text of 6 and not 36. The error gives a distinct count larger than the total, which is the kind of answer the second counting route catches immediately — and which is why the panel computes both.

Taking the round count as a measurement of log2 nThe loop exits when the ranks are all distinct, so the rounds are at most the ceiling of log2 n and often fewer: 1 for abcdefgh, where log2 8 is 3. The bound is the ceiling and the count is what this text needed, which is the same distinction every page of this course draws.

Check your understanding

✓

Finish when you can build both arrays by hand for a short text and read the two answers off them with their proofs.

You should be able to sort the suffixes and give sa, fill the LCP array over neighbours only and justify why neighbours suffice, read the longest repeat off the largest entry, compute the distinct count both by the identity and rank by rank, and say why the number of doubling rounds can be below the ceiling.

Note: That is the whole course: four matchers that read the text once, a hash that replaces comparison with arithmetic and has to verify, one structure that searches for a dictionary in a single scan, and one that preprocesses the text so that questions can be asked afterwards. Every count on every one of those pages was produced by running the algorithm on the input shown, and every page put a proved bound beside it — because the ranking of these methods changed three times across this course while not one of the bounds moved.