Why this matters when you build with AI
Many AI products keep long text: a support log, a code base, a set of meeting transcripts. A common job is to find where a piece of text repeats, or to put two substrings of that text in order. A step that finds the longest passage repeated in a document, or that drops near-copies of a log line, asks these questions again and again over the same large text.
A suffix array answers them fast. It stores every suffix of the text in sorted order, and a companion array stores how much neighbouring suffixes share. Once both are built, a question such as "are these two substrings equal, and which one comes first?" takes a few array lookups. Building the arrays costs more than one scan of the text, so the work pays off only when you ask many questions about the same text.
The risk is in the build. A wrong suffix array looks plausible: it has the right length and the right numbers, only in the wrong order. Every sample in this lesson is checked against a naive version that sorts the suffixes directly, and you should check your own code the same way.
The idea
Suffixes and their order
A suffix of a string s of length n is the part from position i to the end, written s[i..n) in this lesson. The string banana has six suffixes: banana, anana, nana, ana, na and a. Each suffix is identified by its start position, so the suffix starting at position 3 is ana. Positions are counted from 0.
The suffix array sa lists the start positions in the order of their suffixes. For banana the sorted suffixes are a, ana, anana, banana, na, nana, so sa = [5, 3, 1, 0, 4, 2].
The rank array is the inverse. rank[i] is the place of suffix i in sa. Here rank[0] = 3, because suffix 0 is the fourth smallest.
Two facts make the arrays useful:
- A substring is a prefix of some suffix. The substring
anaat position 1 is the start of suffix 1. So all occurrences ofanaare the suffixes whose first three letters areana, and those suffixes sit next to each other insa. - Neighbouring suffixes share a prefix. The longest common prefix (LCP, the longest run of letters that two strings start with) of suffixes
sa[r-1]andsa[r]is stored in the LCP array at indexr.
Define lcp[r] as the LCP of sa[r-1] and sa[r], with lcp[0] = 0. For banana this gives lcp = [0, 1, 3, 0, 0, 2]. The suffixes a and ana share 1 letter, ana and anana share 3, and na and nana share 2.
A worked example: which substring is smaller
Take the substrings s[1..3) = an and s[3..5) = an. They are equal. Now take s[0..3) = ban and s[2..5) = nan. The first letters differ, so ban is smaller. A comparison has to find the first position where the two strings differ. The LCP of the two suffixes gives that position directly. The LCP of suffixes 0 and 2 is 0, so the first letters decide: b is smaller than n.
Comparing two substrings of length k then needs three steps. Find the LCP of their two suffixes. If the LCP is at least k, the substrings are equal over k letters, and the shorter one is smaller only if the lengths differ. If the LCP is shorter than k, compare the letters at that offset.
The standard technique: prefix doubling
Prefix doubling sorts the suffixes by their first 1 character, then by their first 2, then by their first 4, and so on. After round h, the suffixes are sorted by their first 2^h characters. Each round uses only the ranks from the round before, so no two strings are ever compared letter by letter in a long loop.
Here is the order of the cyclic shifts of banana$ after each round. $ is a sentinel, a character smaller than every letter. The numbers come from a real run of a short script.
first 1 char(s): 6:$ 1:a 3:a 5:a 0:b 2:n 4:n
first 2 char(s): 6:$b 5:a$ 1:an 3:an 0:ba 2:na 4:na
first 4 char(s): 6:$ban 5:a$ba 3:ana$ 1:anan 0:bana 4:na$b 2:nanaRead the first line. Sorting by the first character gives $, then the three starts with a, then b, then n. Ties are shown in arbitrary order, because the sort does not yet know their order. The second line breaks the ties on a by the second character: a$ comes before an, and the two an entries stay tied. The third line breaks the rest.
The sentinel matters. It is a character that never appears inside the text and sorts before everything, so a suffix that is a prefix of another suffix comes first. The code sorts cyclic shifts, which wrap around the end, and the sentinel stops the wrap from making a short suffix look like a longer one.
The code
The implementation below sorts the cyclic shifts of s + '\0'. Each round is a counting sort over a small set of classes, so one round is linear. The loop runs at most about log2(n) times, which gives O(n log n) in total. The first round uses the characters themselves as classes. Each later round sorts the shifts by the pair (class of the first half, class of the second half). It sorts the second halves first, then does a stable counting sort on the first halves, which gives the pair order without a comparison sort.
// Suffix array, LCP array, sparse table and substring comparison.
// Input bytes must be 1..255 (the code appends the byte 0 as a sentinel).
#include <bits/stdc++.h>
// Sorts the cyclic shifts of s (s must end with a unique smallest character).
// Prefix doubling: after round h, the classes describe the first 2^h characters.
inline std::vector<int> sort_cyclic_shifts(const std::string& s) {
int n = s.size();
const int alphabet = 256;
std::vector<int> p(n), c(n), cnt(std::max(alphabet, n), 0);
for (int i = 0; i < n; i++) cnt[(unsigned char)s[i]]++;
for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) p[--cnt[(unsigned char)s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i = 1; i < n; i++) {
if (s[p[i]] != s[p[i - 1]]) classes++;
c[p[i]] = classes - 1;
}
std::vector<int> pn(n), cn(n);
for (int h = 0; (1 << h) < n; h++) {
int step = 1 << h;
// Sort by the second half first: shifting p by 2^h gives the order of the second halves.
for (int i = 0; i < n; i++) {
pn[i] = p[i] - step;
if (pn[i] < 0) pn[i] += n;
}
// Stable counting sort by the first half's class.
std::fill(cnt.begin(), cnt.begin() + classes, 0);
for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
for (int i = 1; i < classes; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
// Give new classes to the sorted pairs (first half, second half).
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i < n; i++) {
std::pair<int, int> cur = {c[p[i]], c[(p[i] + step) % n]};
std::pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + step) % n]};
if (cur != prev) classes++;
cn[p[i]] = classes - 1;
}
c.swap(cn);
if (classes == n) break;
}
return p;
}
// suffix_array[i] is the start of the i-th smallest suffix of s.
inline std::vector<int> suffix_array(const std::string& s) {
std::vector<int> p = sort_cyclic_shifts(s + '\0');
// The sentinel suffix is always first, so drop it.
return std::vector<int>(p.begin() + 1, p.end());
}
// lcp[r] = length of the longest common prefix of suffixes sa[r-1] and sa[r]; lcp[0] = 0.
// Kasai's method: the match length drops by at most 1 when the start moves right by 1.
inline std::vector<int> build_lcp(const std::string& s, const std::vector<int>& sa) {
int n = s.size();
std::vector<int> rank(n), lcp(n, 0);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) {
h = 0;
continue;
}
int j = sa[rank[i] - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rank[i]] = h;
if (h > 0) h--;
}
return lcp;
}
// Static range-minimum queries in O(1) after O(n log n) preprocessing.
struct SparseMin {
std::vector<std::vector<int>> t;
std::vector<int> lg;
explicit SparseMin(const std::vector<int>& a) : lg(a.size() + 1, 0) {
int n = a.size();
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
t.push_back(a);
for (int k = 1; (1 << k) <= n; k++) {
t.push_back(std::vector<int>(n - (1 << k) + 1));
for (int i = 0; i + (1 << k) <= n; i++)
t[k][i] = std::min(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
}
}
// Minimum of a[l..r] inclusive. Requires l <= r.
int query(int l, int r) const {
int k = lg[r - l + 1];
return std::min(t[k][l], t[k][r - (1 << k) + 1]);
}
};
struct SuffixIndex {
std::string s;
std::vector<int> sa, rank_, lcp;
SparseMin rmq;
explicit SuffixIndex(std::string str)
: s(std::move(str)), sa(suffix_array(s)), rank_(s.size()), lcp(build_lcp(s, sa)), rmq(lcp) {
for (int i = 0; i < (int)sa.size(); i++) rank_[sa[i]] = i;
}
// Length of the longest common prefix of suffix a and suffix b.
int lcp_suffixes(int a, int b) const {
if (a == b) return (int)s.size() - a;
int ra = rank_[a], rb = rank_[b];
if (ra > rb) std::swap(ra, rb);
return rmq.query(ra + 1, rb);
}
// Compare s[a, a+la) with s[b, b+lb). Returns -1, 0 or 1.
int compare(int a, int la, int b, int lb) const {
int k = std::min(la, lb);
int L = lcp_suffixes(a, b);
if (L >= k) return la == lb ? 0 : (la < lb ? -1 : 1);
return s[a + L] < s[b + L] ? -1 : 1;
}
};The suffix_array function drops the first entry, because the sentinel suffix always comes first and is not part of the answer. The code requires that every input byte is between 1 and 255, because byte 0 is the sentinel.
Kasai's method for the LCP array
Computing the LCP of each neighbouring pair by direct comparison can cost O(n^2). A text of aaaa...a is the bad case. Kasai's method computes all the neighbour LCPs in O(n) in total.
Its idea is this. Let h be the LCP between suffix i and its predecessor j in sa. Then suffix i + 1 and suffix j + 1 share h - 1 letters, because removing the first letter from two strings that share h letters leaves h - 1 shared letters. The predecessor of suffix i + 1 in sa shares at least h - 1 letters with it. So h drops by at most one when i moves right by one. Over the whole run, h rises by one per letter comparison and drops at most once per position, so the total work is at most about 2n.
The build_lcp function in the code above follows that idea. It walks i from 0 to n - 1, and h never goes below 0. When rank[i] is 0, suffix i has no predecessor, so h is reset to 0.
Answering LCP queries with a sparse table
The LCP of the suffixes at ranks l < r equals the minimum of lcp[l+1..r]. Here is why. Moving along sa from one rank to the next can only keep or lose shared letters, never gain them. So the LCP of two ranks cannot be longer than the smallest step between them.
A range minimum query asks for the smallest value in a range of an array. A sparse table answers it in O(1) after O(n log n) preprocessing. The table stores, for each power 2^k and each start i, the minimum of the block of length 2^k that starts at i. A query covers the range with two blocks of the largest power length that fits, and the blocks may overlap. Overlap is safe for a minimum, because the same value is counted twice without changing the answer.
The SparseMin struct in the code above is that table. SuffixIndex puts the arrays together, and its compare method answers the question from the worked example.
Worked problem: compare substrings
Statement (my own). You get a text s of length n, with 1 <= n <= 200000, made of lowercase letters. Then you get q queries, with 1 <= q <= 200000. Each query has three integers a, b and len, counted from 0, with a + len <= n and b + len <= n. For each query print = if the substrings s[a..a+len) and s[b..b+len) are equal, < if the first is smaller in alphabetical order, and > otherwise. After the answers, print the suffix array and the LCP array, so you can check the arrays by hand.
Input format. The first line holds s. The second line holds q. Each of the next q lines holds a b len.
Sample input, from the file sample.txt:
banana
4
1 3 2
0 2 3
3 5 1
0 1 1Expected output, from the program run on this input:
=
<
=
>
suffix array: 5 3 1 0 4 2
lcp array: 0 1 3 0 0 2Check it by hand. Query 1 compares an with an, so =. Query 2 compares ban with nan, so <. Query 3 compares a with a, so =. Query 4 compares b with a, so >. The suffix array and LCP array match the table in the idea section.
The program is:
#include "sa.h"
using namespace std;
// Worked problem: read s, then q queries "a b len" (0-indexed starts, same length).
// For each query print "=" if s[a..a+len) equals s[b..b+len), "<" or ">" otherwise.
int main() {
string s;
cin >> s;
SuffixIndex idx(s);
int q;
cin >> q;
while (q--) {
int a, b, len;
cin >> a >> b >> len;
int c = idx.compare(a, len, b, len);
cout << (c == 0 ? "=" : c < 0 ? "<" : ">") << "\n";
}
cout << "suffix array:";
for (int x : idx.sa) cout << ' ' << x;
cout << "\nlcp array:";
for (int x : idx.lcp) cout << ' ' << x;
cout << "\n";
}The program builds a SuffixIndex once, in O(n log n), and then answers each query in O(1). The total time is O(n log n + q).
Complexity
suffix_array(prefix doubling): O(n log n) time, O(n) memory.build_lcp(Kasai): O(n) time, O(n) memory.SparseMin: O(n log n) time and memory to build, O(1) per query.compare: O(1) per call.
I measured the build on my test machine (WSL2 Linux, g++ 15.2, -O2). Your numbers will differ. The output below prints the time to build the whole SuffixIndex for a random text and for an all-a text, at two lengths.
n=200000 random: build 0.083 s
n=200000 all-a: build 0.049 s
n=2000000 random: build 3.369 s
n=2000000 all-a: build 1.472 sTen times the length took about 14 times as long on the random text. The growth is a bit faster than the length, as the log factor and memory access costs both predict. On this run the all-a text was faster. I did not measure why.
The SA-IS method, briefly
SA-IS is a family of methods that builds the suffix array in linear time. It sorts a subset of the suffixes and then induces the order of the rest. Many fast libraries use it. Its code is much longer than prefix doubling. This lesson does not implement it, and I did not test an implementation, so I make no claim about its speed beyond the linear bound that its authors describe.
Prefix doubling is the right choice for contests and for most text sizes. Switch to a linear method only when profiling shows the build is the bottleneck.
Where AI tools go wrong
An AI assistant can write a suffix array in a few seconds, and the code often looks right. The usual errors are these: it leaves out the sentinel, it sorts the substrings directly with substr, which is correct but too slow and memory-heavy on large input, and it shifts the LCP index by one. These errors do not always crash. They give a plausible order that is wrong for some texts.
Ask for the code and for a test in the same request, then run the test on small random inputs. A prompt that works well:
Write a C++17 suffix array for a lowercase string using prefix doubling with counting sort.
Also write a brute-force version that sorts the suffixes with substr.
Then write a test that generates 20000 random strings of length 1 to 40 over a 2-letter alphabet,
and compares the two suffix arrays, the LCP array (Kasai against a direct count), and 60 random
substring comparisons per string. Print the first mismatch with the string that caused it.
A good answer compiles with -O2, prints one line per run, and has no comparison of the two
arrays outside the test. Check that the brute-force version is the one you trust, not the fast one.Common mistakes
Forgetting the sentinel
Symptom: the suffix array is in the wrong order when one suffix is a prefix of another. Here is real output from the same code with the sentinel removed. The first column is the input. no sentinel is the cyclic sort without '\0'. correct SA is the code above.
ab no sentinel: 0 1 correct SA: 0 1
aa no sentinel: 0 1 correct SA: 1 0
aba no sentinel: 2 0 1 correct SA: 2 0 1
banana no sentinel: 5 3 1 0 4 2 correct SA: 5 3 1 0 4 2Read the aa line. The correct suffix array is 1 0, because a (starting at 1) comes before aa (starting at 0). Without the sentinel, the two cyclic shifts of aa are both aa, so they tie, and the tie is broken by position. The output is 0 1, which is wrong. The ab and banana lines look right by luck.
An off-by-one in the LCP array
lcp[r] is the LCP between sa[r-1] and sa[r], not between sa[r] and sa[r+1]. If the index is shifted, the range minimum that compare uses is wrong for some queries. Here is the real output when I shifted the write to lcp[rank[i] - 1] and ran the brute-force test from the exercise below:
LCP mismatch on aaaaaaaaaaa at 1
exit=1The test stops at the first failing string, which is aaaaaaaaaaa, and reports the rank where the arrays differ. A shifted index is easy to miss in a read-through, so test it.
Kasai's reset
When rank[i] == 0, suffix i has no predecessor, so h must be reset to 0 before the next position. If you skip the reset, the next h can be too large, and the comparison loop can read past the end of the string.
Sorting substrings directly
A comparison sort that calls substr on each step is fine as a check on small inputs. On a large input it copies suffixes of length up to n, and if you store them all at once, the memory is O(n^2). Keep that version in the test file only.
Comparing substrings of different lengths
compare must respect the end of each substring. If the LCP is at least the shorter length, the answer depends on the lengths: equal lengths give 0, and the shorter string is smaller otherwise. The code handles this case before it looks at any letter.
Hands-on exercise
Work on your own machine. Create a folder, save sa.h from the code section above into it, save the test below as brute_sa.cpp, and compile:
g++ -O2 -std=c++17 -Wall -Wextra -o brute_sa brute_sa.cpp
./brute_sa#include "sa.h"
using namespace std;
int main() {
mt19937 rng(12345);
long long checks = 0;
for (int iter = 0; iter < 20000; iter++) {
int n = rng() % 40 + 1;
int sigma = rng() % 3 + 1;
string s(n, 'a');
for (char& ch : s) ch = 'a' + rng() % sigma;
SuffixIndex idx(s);
// Naive suffix array: sort the suffixes directly.
vector<int> naive(n);
iota(naive.begin(), naive.end(), 0);
sort(naive.begin(), naive.end(), [&](int x, int y) { return s.substr(x) < s.substr(y); });
if (naive != idx.sa) { printf("SA mismatch on %s\n", s.c_str()); return 1; }
// Naive LCP between neighbours.
for (int r = 1; r < n; r++) {
int a = naive[r - 1], b = naive[r], L = 0;
while (a + L < n && b + L < n && s[a + L] == s[b + L]) L++;
if (L != idx.lcp[r]) { printf("LCP mismatch on %s at %d\n", s.c_str(), r); return 1; }
}
// Random substring comparisons.
for (int q = 0; q < 60; q++) {
int a = rng() % n, b = rng() % n;
int la = rng() % (n - a) + 1, lb = rng() % (n - b) + 1;
string x = s.substr(a, la), y = s.substr(b, lb);
int want = x < y ? -1 : (x > y ? 1 : 0);
if (idx.compare(a, la, b, lb) != want) { printf("compare mismatch on %s\n", s.c_str()); return 1; }
checks++;
}
}
printf("all tests passed: 20000 strings, %lld substring comparisons\n", checks);
return 0;
}A correct build prints this line, with the same numbers if you use the same generator seed:
all tests passed: 20000 strings, 1200000 substring comparisonsThen do three things. First, change rng() % 3 + 1 in the sigma line to rng() % 4 + 1, so the alphabet has four letters, and confirm the test still passes. Second, change the lcp[rank[i]] = h; line to write at rank[i] - 1, and confirm the test fails as shown in the mistakes section. Third, write a version of compare that returns the answer from the lcp array with a sparse table query, and check it against the naive substr comparison.
Checklist
- Is the sentinel byte 0 appended exactly once, and are all input bytes from 1 to 255?
- Does
sahave length n and hold each start position exactly once? - Are neighbouring suffixes in
sain increasing order? Check it with the naive comparison on small inputs. - Is
lcp[0]equal to 0? - Does
lcp_suffixes(a, a)return the length of suffixa, not an error? - Does the random test pass with a 2-letter alphabet? That alphabet has the most repeats, so it finds the most bugs.
Practice
Practice 1: the arrays for mississippi
Write sa and lcp for mississippi, by hand or with the code. Then use the sparse table to find the LCP of suffixes 1 and 4.
Hint: sort the eleven suffixes first, and keep track of the rank of each start position. The LCP of two suffixes is the minimum of lcp over the range from the lower rank plus 1 to the higher rank.
Show the answer
The suffix array is 10 7 4 1 0 9 8 6 3 5 2 and the LCP array is 0 1 1 4 0 0 1 0 2 1 3. Suffix 1 has rank 3, and suffix 4 has rank 2, because index 2 of sa holds 4 and index 3 holds 1. The range is lcp[3..3], which holds 4. So the LCP of suffixes 1 and 4 is 4: the shared text is issi. I checked this with the lcp_suffixes method on the real SuffixIndex.
Practice 2: count occurrences of a pattern
Write a function that counts how many times pattern p occurs in s, using two binary searches on sa. The suffixes that start with p form one block of ranks.
Hint: the first search finds the first rank whose first m letters are at least p. The second search finds the first rank whose first m letters are greater than p. Compare the truncated substrings, because a suffix can be shorter than m.
Show the answer
Here is the solution:
#include "sa.h"
using namespace std;
// Count occurrences of p: the suffixes starting with p form one block of ranks.
// lower = first rank whose length-m prefix is >= p, upper = first rank whose length-m prefix is > p.
int count_by_sa(const SuffixIndex& idx, const string& p) {
int n = idx.s.size(), m = p.size();
auto prefix_at = [&](int r) { return idx.s.substr(idx.sa[r], m); }; // truncated at the end
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prefix_at(mid) < p) lo = mid + 1; else hi = mid;
}
int lower = lo;
lo = lower; hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prefix_at(mid) <= p) lo = mid + 1; else hi = mid;
}
return lo - lower;
}
int main() {
mt19937 rng(99);
int bad = 0, tests = 0;
for (int it = 0; it < 3000; it++) {
int n = rng() % 25 + 1, sigma = rng() % 3 + 1;
string s(n, 'a');
for (char& ch : s) ch = 'a' + rng() % sigma;
SuffixIndex idx(s);
for (int q = 0; q < 30; q++) {
int m = rng() % 4 + 1;
string p(m, 'a');
for (char& ch : p) ch = 'a' + rng() % (sigma + 1);
long long want = 0;
for (int i = 0; i + m <= n; i++) want += s.compare(i, m, p) == 0;
tests++;
if (count_by_sa(idx, p) != want) bad++;
}
}
printf("practice A: %d tests, %d mismatches\n", tests, bad);
SuffixIndex mis("mississippi");
for (string p : {"ssi", "is", "i", "pp", "mississippi", "x", "ssippi"})
printf("count of %s = %d\n", p.c_str(), count_by_sa(mis, p));
}Its real output:
practice A: 90000 tests, 0 mismatches
count of ssi = 2
count of is = 2
count of i = 4
count of pp = 1
count of mississippi = 1
count of x = 0
count of ssippi = 1The program ran 90000 random queries against a naive count, with no mismatch. The is count is 2, because the i at position 7 is followed by p, not s.
Practice 3: why the sentinel is needed
Explain in one paragraph why the output for aa without the sentinel is 0 1, and say what the correct output is.
Hint: think about the cyclic shifts of aa, and about what a sort does with two equal keys.
Show the answer
The two cyclic shifts of aa are both aa, so the sort sees two equal keys. It keeps their input order, which puts start 0 first. But suffix a (start 1) is a prefix of aa, and it must come first. With the sentinel, the suffixes become a$ and aa$. Comparing them, the second letter is $ against a, and $ is smaller, so a$ comes first. The correct suffix array is 1 0.
Practice 4: a substring comparison without the code
In banana, compare the substrings s[0..4) = bana and s[2..5) = nan using only the LCP of their suffixes.
Hint: find the LCP of suffix 0 and suffix 2. Then look at the first letter where the two substrings differ.
Show the answer
Suffix 0 is banana and suffix 2 is nana. Their LCP is 0, because the first letters b and n differ. The LCP is 0, which is less than the shorter length 3, so the comparison is decided by the letter at offset 0. The letter b is smaller than n, so bana is smaller than nan. The answer is <.
Summary
Sort the suffixes by prefix doubling, add the LCP array with Kasai's method, and answer each comparison with one range minimum. The next lesson builds a different index, the suffix automaton, for membership and counting questions.