SyntaxPilot
Courses/Competitive Programming/Lesson 77
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 77 of 90

Suffix array and LCP

queued

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. banana has six: banana, anana, nana, ana, na, a.
  • Every substring is a prefix (a start) of some suffix. ana is the start of anana and of ana.
  • 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_ → sorted a_ 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::sort of 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 by sa[r] and sa[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/ana share 3, so nana/na share ≥ 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 0 if 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

  1. What is a suffix array? The start positions of all suffixes of a string, in sorted order of the suffixes.
  2. What is the LCP array? For each pair of neighbouring suffixes in sorted order, the length of their longest common prefix.
  3. 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.
  4. 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.
  5. How do you count distinct substrings? n(n+1)/2 − Σ lcp, in 64-bit arithmetic.
  6. Longest repeated substring? The maximum of the LCP array.
  7. 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