Suffix Array
Sort all suffixes once, then reuse the order and LCP information for many substring and lexicographic queries.
Suffix Array
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Suffix array is the static full-string structure I want when the problem is about lexicographic order of suffixes, substring comparison, or repeated substrings, but I still want something lighter than a suffix tree.
Problem-Driven Motivation
Suppose a problem asks for one of the following on a string of length \(n \le 2 \cdot 10^5\):
count distinct substrings,
find the lexicographically smallest occurrence of a pattern,
analyze repeated substrings,
compare many substrings lexicographically.
The naive view is to work directly with substrings, but there are \(O(n^2)\) of them. The structural observation is that every substring is a prefix of some suffix. Once all suffixes are sorted, a lot of substring logic becomes local.
Recognition Pattern
Suffix array is a strong fit when:
the string is static,
lexicographic suffix order matters,
pattern search by binary search is acceptable,
repeated-substring questions reduce to common prefixes of nearby suffixes.
Signals that usually point here:
``sort suffixes / rotations'',
``count distinct substrings'',
``longest repeated substring'',
``pattern queries on one fixed text''.
Derivation
The suffix array \(\texttt{sa}\) stores all suffix starting positions in lexicographic order.
The hard part is building it without comparing long suffix strings directly. The doubling algorithm solves this by ranking prefixes of increasing length.
Round \(k\).
Assume we already know the lexicographic classes of all length-\(2^k\) prefixes. Then the first \(2^{k+1}\) characters of suffix \(i\) are summarized by the pair \[ (\texttt{cls}[i], \texttt{cls}[i + 2^k]). \]
So sorting suffixes by their first \(2^{k+1}\) characters becomes sorting pairs of small integers. After enough rounds, the compared length exceeds the string length, so the full suffix order is known.
Why LCP appears naturally.
Once suffixes are sorted, repeated-substring questions are local because two suffixes with a long common prefix must sit next to each other in suffix-array order. That is why the LCP array is almost always built together with \(\texttt{sa}\).
Worked Problem
Problem.
Count the number of distinct substrings of a string \(s\).
Why naive fails.
There are \(O(n^2)\) substrings, and even hashing all of them is usually too expensive at \(n = 2 \cdot 10^5\).
Key observation.
Suffix \(s[sa[i] \dots n-1]\) contributes all of its prefixes as substrings. That is \[ n - sa[i] \] substrings in total. But the first \(\texttt{lcp}[i-1]\) of them were already seen in the previous suffix.
Therefore
Why only adjacent LCPs matter.
In sorted order, the largest already-seen common prefix of the current suffix is always realized by one of its neighbors, so subtracting adjacent LCPs removes exactly the duplicates introduced by ordering.
Implementation Reasoning
The implementation has three moving parts:
append one unique terminator smaller than all real characters,
build \(\texttt{sa}\) with the doubling method,
build \(\texttt{lcp}\) with Kasai's linear scan.
Two practical details matter a lot:
the terminator ensures no suffix is a prefix of another without a clean ordering,
\(\texttt{lcp[i]}\) belongs to adjacent suffixes \(\texttt{sa[i]}\) and \(\texttt{sa[i+1]}\), not to original string positions.
The code returns both arrays and includes a distinct-substring application function.
Correctness Intuition
The doubling invariant is the real proof:
After round \(k\), the class array correctly ranks all prefixes of length \(2^k\).
Sorting pairs of those classes therefore sorts prefixes of length \(2^{k+1}\). Once the compared length covers the whole suffixes, the order is final.
Kasai's algorithm is linear because its matched prefix length only decreases by at most one between consecutive starting positions.
Complexity Analysis
suffix array by doubling: \(O(n \log n)\),
LCP by Kasai: \(O(n)\),
memory: \(O(n)\).
Common Pitfalls
Forgetting the unique terminator.
Misaligning \(\texttt{lcp}\) with suffix-array order.
Using suffix array when the real need is online substring extension, which is more natural for suffix automaton.
Assuming arbitrary substring LCP queries are free without adding an RMQ layer over \(\texttt{lcp}\).
Variants and Failure Modes
Add RMQ over \(\texttt{lcp}\) for fast LCP queries between arbitrary suffixes.
Use suffix automaton when the string grows online or substring occurrence aggregation is more natural.
SA-IS gives linear construction, but the contest constant and implementation complexity are much higher.
Practice Problems
Count distinct substrings.
Find the longest repeated substring.
Pattern existence and lexicographic substring queries on a fixed string.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
pair<vector<int>, vector<int>> build_suffix_array(const string& original) {
string s = original + '$';
int n = (int)s.size();
vector<int> sa(n), cls(n);
{
vector<pair<char, int>> initial(n);
for (int i = 0; i < n; ++i) initial[i] = {s[i], i};
sort(initial.begin(), initial.end());
for (int i = 0; i < n; ++i) sa[i] = initial[i].second;
cls[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
cls[sa[i]] = cls[sa[i - 1]] + (initial[i].first != initial[i - 1].first);
}
}
for (int k = 0; (1 << k) < n; ++k) {
for (int i = 0; i < n; ++i) {
sa[i] = (sa[i] - (1 << k) + n) % n;
}
vector<int> cnt(n, 0), next_sa(n);
for (int x : cls) ++cnt[x];
for (int i = 1; i < n; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) {
next_sa[--cnt[cls[sa[i]]]] = sa[i];
}
sa = next_sa;
vector<int> next_cls(n);
next_cls[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
pair<int, int> cur = {cls[sa[i]], cls[(sa[i] + (1 << k)) % n]};
pair<int, int> prev = {cls[sa[i - 1]], cls[(sa[i - 1] + (1 << k)) % n]};
next_cls[sa[i]] = next_cls[sa[i - 1]] + (cur != prev);
}
cls = next_cls;
}
sa.erase(sa.begin()); // remove suffix starting at '$'
int m = (int)sa.size();
vector<int> rank(m), lcp(max(0, m - 1), 0);
for (int i = 0; i < m; ++i) rank[sa[i]] = i;
for (int i = 0, common = 0; i < m; ++i) {
if (rank[i] == m - 1) {
common = 0;
continue;
}
int j = sa[rank[i] + 1];
while (i + common < m && j + common < m && original[i + common] == original[j + common]) {
++common;
}
lcp[rank[i]] = common;
if (common) --common;
}
return {sa, lcp};
}
// Example application: number of distinct substrings.
long long count_distinct_substrings_with_sa(const string& s) {
pair<vector<int>, vector<int>> result = build_suffix_array(s);
const vector<int>& sa = result.first;
const vector<int>& lcp = result.second;
long long total = 0;
for (int pos : sa) total += (int)s.size() - pos;
for (int x : lcp) total -= x;
return total;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.