These are the notes for Competitive Programming episode 77. A suffix array lists every suffix of a string in sorted order (stored as the suffixes' start positions), and the LCP array stores how many first letters each suffix shares with the one sorted just before it. Together they answer questions about all substrings at once, because every substring is the start of some suffix. Distinct Snippets (count the different substrings) shows a letter-by-letter suffix sort that is right but TLE on 200000 a's, then prefix doubling (sort by the first 1, 2, 4, 8 … letters using ranks) and Kasai's algorithm (the LCP array in O(n)). A real bug: int total = n * (n + 1) / 2 prints 672125747 instead of 19999478579. Echo (the longest substring that appears twice) is just the largest LCP. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
The index at the back of a book lists every entry alphabetically with its page number: that is the suffix array (sorted, with positions). Neighbouring entries share their start (chai, chai stall, chai tea): that shared part is the LCP. A smart editor never compares entries letter by letter: she sorts by the first word, then breaks ties by the next word, reusing the order she already has (prefix doubling). And any phrase in the book is the start of some entry, so one sorted list answers questions about every piece of text.
Problem S1 · Distinct Snippets
(Written for this course.)
- A string s of lowercase letters, 1 ≤ |s| ≤ 2·10^5.
- Print the number of different non-empty substrings of s (a substring is a continuous piece; repeats count once).
banana
banana has 21 substrings with repeats; the different ones are b, a, n, ba, an, na, ban, ana, nan, bana, anan, nana, banan, anana, banana: 15.
Why we can't list them
A string of length n has n(n+1)/2 substrings counting repeats: about 2·10^10 for n = 2·10^5. We have to count the repeats without listing anything.
The key observation
- A suffix is the string from position i to the end.
bananahas six: banana, anana, nana, ana, na, a. - Every substring is a prefix (a start) of some suffix.
anais the start ofananaand ofana. - Sort the suffixes:
a · ana · anana · banana · na · nana. The number of first letters each one shares with the one before it is the LCP (longest common prefix):1 · 3 · 0 · 0 · 2, sum 6. - Each suffix of length L brings L substrings (its prefixes), but the first LCP of them were already brought by its neighbour. So
distinct substrings = n(n+1)/2 − Σ lcp → 21 − 6 = 15.
| sorted position r | sa[r] | suffix | lcp with the previous |
|---|---|---|---|
| 0 | 5 | a | — |
| 1 | 3 | ana | 1 |
| 2 | 1 | anana | 3 |
| 3 | 0 | banana | 0 |
| 4 | 4 | na | 0 |
| 5 | 2 | nana | 2 |
Attempt 1: sort the suffixes letter by letter (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int common(const string& s, int a, int b) { // letters shared by two suffixes
int h = 0;
while (a + h < (int)s.size() && b + h < (int)s.size() && s[a + h] == s[b + h]) h++;
return h;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](int a, int b) { // compare two suffixes letter by letter
int h = common(s, a, b);
if (a + h == n || b + h == n) return a + h == n && b + h != n;
return s[a + h] < s[b + h];
});
ll total = (ll)n * (n + 1) / 2;
for (int i = 0; i + 1 < n; i++) total -= common(s, sa[i], sa[i + 1]);
cout << total << "\n";
}
15
Correct, but on 200000 a's (string s(200000, 'a'); instead of reading s) two suffixes share almost everything, so one comparison reads up to 10^5 letters and the sort makes millions of comparisons: O(n² log n). The SyntaxPilot compiler stops it with Time Limit Exceeded.
Prefix doubling: sort by 1, 2, 4, 8 … letters
- Let
rk[i]be the rank of suffix i by its first k letters (equal starts get equal ranks). - The first 2k letters of suffix i are its first k letters followed by the first k letters of suffix i + k. So sort by the pair
(rk[i], rk[i + k]), using −1 when i + k runs past the end (a shorter string comes first). banana, k = 1 (first two letters):ba an na an na a_→ sorteda_ an an ba na na.- Stop as soon as all n ranks are different: at most ⌈log₂ n⌉ rounds (about 18 for 2·10^5).
- Each round is one
std::sortof n indices with O(1) comparisons: O(n log² n) in total. (A radix sort per round gives O(n log n); SA-IS is O(n).)
Kasai's algorithm: the LCP array in O(n)
lcp[r]= the letters shared bysa[r]andsa[r + 1].- Visit the suffixes in text order, i = 0, 1, 2 …, and keep the shared length h.
- If suffix i shares h letters with the suffix sorted just before it, then suffix i + 1 shares at least h − 1 with the suffix sorted just before it (drop the first letter of both:
anana/anashare 3, sonana/nashare ≥ 2). - So after each suffix do
if (h > 0) h--;and only extend from there. h decreases at most n times and never exceeds n, so it increases at most 2n times: O(n).
The int overflow bug
Here is the full solution, but with the total in int:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
int total = n * (n + 1) / 2; // every substring, with repeats
for (int x : lcp) total -= x; // minus the repeated starts
cout << total << "\n";
}
On the sample it is right:
15
On 200000 random letters (generated in the program with mt19937 gen(77)) the answer is about 2·10^10, which does not fit in an int (max 2147483647). The real output is a wrapped number:
672125747
The fix: long long, cast before multiplying
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
ll total = (ll)n * (n + 1) / 2; // every substring, with repeats
for (int x : lcp) total -= x; // minus the repeated starts
cout << total << "\n";
}
15
The same 200000 random letters:
19999478579
200000 a's (one distinct substring per length):
200000
Edge case, a single letter:
z
1
Stress test
Compare against a set<string> holding every substring, on 500 random strings of up to 12 letters over abc:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
mt19937 gen(77);
for (int it = 1; it <= 500; it++) {
string s(gen() % 12 + 1, 'a');
for (char& c : s) c = 'a' + gen() % 3;
set<string> all; // brute force: every substring
for (int i = 0; i < (int)s.size(); i++)
for (int len = 1; i + len <= (int)s.size(); len++) all.insert(s.substr(i, len));
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
ll fast = (ll)s.size() * (s.size() + 1) / 2;
for (int x : lcp) fast -= x;
if ((ll)all.size() != fast) { cout << "mismatch on " << s; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem S2 · Echo
(Written for this course.)
- A string s, 1 ≤ |s| ≤ 2·10^5. Print the length of the longest substring that appears at least twice (the copies may overlap) and that substring (any one if several); print
0if no letter repeats.
Observation. A substring that appears twice is the start of two different suffixes. In sorted order, the two suffixes sharing the longest start are neighbours (anything sorted between them shares at least as much with both). So the answer is the largest value in the LCP array, and sa[i] tells where it starts.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
int best = 0, at = 0;
for (int i = 0; i + 1 < n; i++) // neighbours share the most
if (lcp[i] > best) best = lcp[i], at = sa[i];
cout << best << " " << s.substr(at, best) << "\n";
}
chaichaipani
4 chai
banana (the two copies of ana overlap, which is allowed):
3 ana
aaaa:
3 aaa
chai (nothing repeats; the substring is empty):
0
Complexity vs the constraints
| Method | Time | Verdict for n = 2·10^5 |
|---|---|---|
| list every substring in a set | O(n³) time, O(n²) memory | hopeless |
| sort suffixes letter by letter | O(n² log n) | TLE on repetitive strings |
prefix doubling with std::sort |
O(n log² n) ≈ 6·10^7 comparisons | accepted |
| prefix doubling with radix sort | O(n log n) | accepted |
| SA-IS | O(n) | for n ~ 10^6 and more |
| Kasai's LCP | O(n) | accepted |
Memory: a few arrays of n ints (under 5 MB).
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int total = n * (n + 1) / 2 |
672125747 instead of 19999478579 |
2·10^10 overflows int |
ll total = (ll)n * (n + 1) / 2 |
| comparing suffixes letter by letter | Time Limit Exceeded | O(n) per comparison | prefix doubling with ranks |
h = 0 for every suffix in Kasai |
correct but TLE on aaaa… |
re-reads shared letters: O(n²) | if (h > 0) h--; |
reading rk[i + k] when i + k ≥ n |
Runtime Error / garbage | outside the array | use −1 (shorter first) |
lcp of size n with an unused slot |
off-by-one sums | n suffixes have n − 1 neighbour pairs | size max(n − 1, 0) |
| stopping after a fixed number of rounds | Wrong Answer on long strings | ranks not yet all different | stop when rk[sa[n − 1]] == n − 1 |
Mini project
A tiny "phrase finder". Read a paragraph (letters only), build its suffix array once, then answer queries "does phrase p occur, and how many times?" with two binary searches over sa[] (the suffixes starting with p form one contiguous block). Print the block size. Compare its speed with find in a loop on a long paragraph.
Practice
These are the homework problems from the episode.
1. Count the distinct substrings that appear at least twice. Going down the sorted suffixes, the pair (r, r + 1) adds max(0, lcp[r] − lcp[r − 1]) new repeated substrings: the repeated starts it shares that the previous pair did not.
Solution (checked against a brute force on 300 random strings)
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() { // distinct substrings that appear at least twice
string s;
cin >> s;
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
long long total = 0;
for (int i = 0; i < (int)lcp.size(); i++) // new repeated starts this neighbour pair adds
total += max(0, lcp[i] - (i ? lcp[i - 1] : 0));
cout << total << "\n";
}
5
For banana the repeated substrings are a, an, ana, n, na: 5.
2. Longest common substring of two strings. Join them as a + "#" + b; # is smaller than every letter and appears once, so no common prefix crosses it. The answer is the largest LCP between neighbours that come from different strings.
Solution (checked against a brute force on 300 random pairs)
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() { // longest common substring of a and b
string a, b;
cin >> a >> b;
string s = a + "#" + b; // '#' stops a common prefix at the join
int n = s.size(), na = a.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
int best = 0, at = 0;
for (int i = 0; i + 1 < n; i++)
if ((sa[i] < na) != (sa[i + 1] < na) && lcp[i] > best) // one suffix from a, one from b
best = lcp[i], at = sa[i];
cout << best << " " << s.substr(at, best) << "\n";
}
4 chai
3. The k-th smallest distinct substring. Suffix sa[r] contributes the substrings of lengths lcp[r − 1] + 1 … n − sa[r], in sorted order. Walk r upwards subtracting these counts from k.
Hint
When k fits inside suffix r's block, the answer is s.substr(sa[r], lcp[r − 1] + k). Use long long for k.
4. Does pattern p occur in s? The suffixes that start with p form one contiguous block of sa[]. Binary search for its first and last position, comparing p with s.compare(sa[mid], |p|, p): O(|p| log n) per query.
Hint
lower_bound with a comparator that compares the first |p| letters of a suffix with p; the count of occurrences is the block's size.
Quick quiz
// s = "abab"
// sorted suffixes: ab, abab, b, bab
// distinct substrings = ?
A) 7 · B) 10 · C) 8 · D) 6
Answer
A. n(n+1)/2 = 10. The LCPs of the neighbours are ab|abab = 2, abab|b = 0, b|bab = 1, which sum to 3. 10 − 3 = 7: a, b, ab, ba, aba, bab, abab.
Interview questions
- What is a suffix array? The start positions of all suffixes of a string, in sorted order of the suffixes.
- What is the LCP array? For each pair of neighbouring suffixes in sorted order, the length of their longest common prefix.
- How does prefix doubling work? After round k every suffix has a rank by its first k letters; round 2k sorts by the pair (rank of i, rank of i + k). log n rounds.
- Why is Kasai's algorithm linear? Moving from suffix i to i + 1 in text order, the LCP with the previous suffix drops by at most one, so the pointer h moves O(n) times in total.
- How do you count distinct substrings? n(n+1)/2 − Σ lcp, in 64-bit arithmetic.
- Longest repeated substring? The maximum of the LCP array.
- Suffix array vs suffix automaton? Both handle all substrings; the array is sorted (good for order, k-th, binary search), the automaton is built online and walks queries letter by letter (next episode).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Substring | A continuous piece of a string | nan in banana |
| Distinct substrings | Substrings counted once each | banana → 15 |
| Suffix | The string from position i to the end | nana (i = 2) |
| Prefix | The string from the start to some position | ban of banana |
Suffix array sa |
Suffix start positions in sorted order | 5 3 1 0 4 2 |
Rank rk[i] |
The position of suffix i in the current order | ties get equal ranks |
| Prefix doubling | Sorting by 1, 2, 4, 8 … letters with ranks | ~18 rounds for 2·10^5 |
| LCP | Longest common prefix of two strings | LCP(ana, anana) = 3 |
| LCP array | LCP of each pair of sorted neighbours | 1 3 0 0 2 |
| Kasai's algorithm | O(n) LCP: keep h, drop it by one | if (h > 0) h--; |
| Lexicographic order | Dictionary order; a prefix comes first | ab < abab < b |
| Integer overflow | A result too big for its type wraps around | 672125747 |
long long |
64-bit integer, up to about 9.2·10^18 | 19999478579 |
| Radix sort | Sorting by digits/keys in linear passes | O(n log n) suffix array |
| SA-IS | A linear-time suffix array algorithm | for n ≥ 10^6 |
| Stress test | Fast vs brute force on many random inputs | all 500 tests passed |
| Suffix automaton | A small machine for all substrings (next episode) | — |
Summary
- Every substring is a prefix of a suffix; sorting the suffixes puts shared starts next to each other.
- Suffix array by prefix doubling: sort pairs
(rk[i], rk[i + k]), double k, stop when all ranks differ: O(n log² n). - LCP array by Kasai: suffixes in text order, keep h,
h--after each: O(n). - Distinct substrings =
(ll)n * (n + 1) / 2 − Σ lcp; longest repeat =max(lcp).
Solutions in C++, Java and Python
Problem S1 · Distinct Snippets
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
ll total = (ll)n * (n + 1) / 2; // every substring, with repeats
for (int x : lcp) total -= x; // minus the repeated starts
cout << total << "\n";
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int[] suffixArray(String s) { // prefix doubling
int n = s.length();
Integer[] sa = new Integer[n];
int[] rk = new int[n], tmp = new int[n];
for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s.charAt(i); }
for (int k = 1; ; k <<= 1) {
final int K = k; final int[] R = rk;
Comparator<Integer> cmp = (a, b) -> {
if (R[a] != R[b]) return Integer.compare(R[a], R[b]);
int ra = a + K < n ? R[a + K] : -1, rb = b + K < n ? R[b + K] : -1;
return Integer.compare(ra, rb);
};
Arrays.sort(sa, cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);
rk = tmp.clone();
if (rk[sa[n - 1]] == n - 1) break;
}
int[] res = new int[n];
for (int i = 0; i < n; i++) res[i] = sa[i];
return res;
}
static int[] lcpArray(String s, int[] sa) { // Kasai
int n = s.length(), h = 0;
int[] rk = new int[n], lcp = new int[Math.max(n - 1, 0)];
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) {
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1];
while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--;
}
return lcp;
}
public static void main(String[] args) throws IOException {
String s = new BufferedReader(new InputStreamReader(System.in)).readLine().trim();
int[] sa = suffixArray(s), lcp = lcpArray(s, sa);
long n = s.length(), total = n * (n + 1) / 2; // long: up to 2 * 10^10
for (int x : lcp) total -= x;
System.out.println(total);
}
}
15
Python
import sys
def suffix_array(s): # prefix doubling
n = len(s)
rk = [ord(c) for c in s]
sa = list(range(n))
k = 1
while True:
key = lambda i: (rk[i], rk[i + k] if i + k < n else -1)
sa.sort(key=key)
tmp = [0] * n
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]))
rk = tmp
if rk[sa[-1]] == n - 1:
return sa
k <<= 1
def lcp_array(s, sa): # Kasai
n = len(s)
rk = [0] * n
for i, p in enumerate(sa):
rk[p] = i
lcp, h = [0] * max(n - 1, 0), 0
for i in range(n):
if rk[i] == 0:
h = 0
continue
j = sa[rk[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rk[i] - 1] = h
if h:
h -= 1
return lcp
s = sys.stdin.readline().strip()
sa = suffix_array(s)
n = len(s)
print(n * (n + 1) // 2 - sum(lcp_array(s, sa))) # Python ints never overflow
15
Problem S2 · Echo
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> suffixArray(const string& s) { // prefix doubling
int n = s.size();
vector<int> sa(n), rk(n), tmp(n);
for (int i = 0; i < n; i++) sa[i] = i, rk[i] = s[i]; // round 0: rank by the first letter
for (int k = 1; ; k <<= 1) { // now sort by the first 2k letters
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = a + k < n ? rk[a + k] : -1; // rank of the second half
int rb = b + k < n ? rk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break; // all ranks different: done
}
return sa;
}
vector<int> lcpArray(const string& s, const vector<int>& sa) { // Kasai
int n = s.size(), h = 0;
vector<int> rk(n), lcp(max(n - 1, 0)); // lcp[i] = LCP(sa[i], sa[i + 1])
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) { // suffixes in text order
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1]; // the suffix sorted just before
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--; // the next suffix keeps at least h - 1
}
return lcp;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> sa = suffixArray(s), lcp = lcpArray(s, sa);
int best = 0, at = 0;
for (int i = 0; i + 1 < n; i++) // neighbours share the most
if (lcp[i] > best) best = lcp[i], at = sa[i];
cout << best << " " << s.substr(at, best) << "\n";
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int[] suffixArray(String s) { // prefix doubling
int n = s.length();
Integer[] sa = new Integer[n];
int[] rk = new int[n], tmp = new int[n];
for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s.charAt(i); }
for (int k = 1; ; k <<= 1) {
final int K = k; final int[] R = rk;
Comparator<Integer> cmp = (a, b) -> {
if (R[a] != R[b]) return Integer.compare(R[a], R[b]);
int ra = a + K < n ? R[a + K] : -1, rb = b + K < n ? R[b + K] : -1;
return Integer.compare(ra, rb);
};
Arrays.sort(sa, cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);
rk = tmp.clone();
if (rk[sa[n - 1]] == n - 1) break;
}
int[] res = new int[n];
for (int i = 0; i < n; i++) res[i] = sa[i];
return res;
}
static int[] lcpArray(String s, int[] sa) { // Kasai
int n = s.length(), h = 0;
int[] rk = new int[n], lcp = new int[Math.max(n - 1, 0)];
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0; i < n; i++) {
if (rk[i] == 0) { h = 0; continue; }
int j = sa[rk[i] - 1];
while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
lcp[rk[i] - 1] = h;
if (h > 0) h--;
}
return lcp;
}
public static void main(String[] args) throws IOException {
String s = new BufferedReader(new InputStreamReader(System.in)).readLine().trim();
int[] sa = suffixArray(s), lcp = lcpArray(s, sa);
int best = 0, at = 0;
for (int i = 0; i + 1 < s.length(); i++)
if (lcp[i] > best) { best = lcp[i]; at = sa[i]; }
System.out.println(best + " " + s.substring(at, at + best));
}
}
4 chai
Python
import sys
def suffix_array(s): # prefix doubling
n = len(s)
rk = [ord(c) for c in s]
sa = list(range(n))
k = 1
while True:
key = lambda i: (rk[i], rk[i + k] if i + k < n else -1)
sa.sort(key=key)
tmp = [0] * n
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i - 1]] + (key(sa[i - 1]) < key(sa[i]))
rk = tmp
if rk[sa[-1]] == n - 1:
return sa
k <<= 1
def lcp_array(s, sa): # Kasai
n = len(s)
rk = [0] * n
for i, p in enumerate(sa):
rk[p] = i
lcp, h = [0] * max(n - 1, 0), 0
for i in range(n):
if rk[i] == 0:
h = 0
continue
j = sa[rk[i] - 1]
while i + h < n and j + h < n and s[i + h] == s[j + h]:
h += 1
lcp[rk[i] - 1] = h
if h:
h -= 1
return lcp
s = sys.stdin.readline().strip()
sa = suffix_array(s)
lcp = lcp_array(s, sa)
best, at = 0, 0
for i, x in enumerate(lcp):
if x > best:
best, at = x, sa[i]
print(best, s[at:at + best])
4 chai