Suffix Structures

The suffix array: sorting all suffixes of a string and what that gives you.

The suffix array is the sorted list of all suffixes of a string (only their starting positions are stored, of course). It unlocks a whole class of problems: searching for any pattern in O(m log n), counting distinct substrings, the longest common substring of two strings. Building it by naive sorting is O(n² log n): comparing suffixes is slow. The classic trick is sorting by powers of two: sort the suffixes first by their first 1 character, then 2, 4, 8... At every step a suffix is described by a PAIR of equivalence classes from the previous step — and a pair compares in O(1).

Try it yourself — the code is editable

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::string s;
    std::cin >> s;
    s += "$"; // терминальный символ меньше всех букв
    int n = s.size();

std::vector<int> order(n), cls(n);
    for (int i = 0; i < n; i++) order[i] = i;
    std::sort(order.begin(), order.end(), [&](int a, int b) { return s[a] < s[b]; });
    cls[order[0]] = 0;
    for (int i = 1; i < n; i++) {
        cls[order[i]] = cls[order[i - 1]] + (s[order[i]] != s[order[i - 1]] ? 1 : 0);
    }

for (int len = 1; len < n; len *= 2) {
        std::vector<std::pair<std::pair<int, int>, int>> t(n);
        for (int i = 0; i < n; i++) {
            t[i] = {{cls[i], cls[(i + len) % n]}, i};
        }
        std::sort(t.begin(), t.end());

for (int i = 0; i < n; i++) order[i] = t[i].second;
        cls[order[0]] = 0;
        for (int i = 1; i < n; i++) {
            cls[order[i]] = cls[order[i - 1]] + (t[i].first != t[i - 1].first ? 1 : 0);
        }
    }

std::cout << "Суффиксы по алфавиту:\n";
    for (int i = 1; i < n; i++) { // пропускаем суффикс из одного $
        std::cout << s.substr(order[i], n - 1 - order[i]) << "\n";
    }
    return 0;
}

Input (sample — feel free to edit)

The suffix array in O(n log² n). Enter: banana

For banana the suffix order is: a, ana, anana, banana, na, nana. Unpacking the tricks: • the terminal character $ (smaller than every letter) evens the suffixes out into "cyclic shifts" — that is why (i + len) % n works; • an equivalence class is "the group number of equal prefixes of length len"; the pair (class of the start, class of the middle) fully describes a prefix of length 2·len; • with counting sort instead of std::sort you get the classic O(n log n). The topic's next step is the LCP array (lengths of common prefixes of neighboring suffixes, Kasai's algorithm in O(n)): with it you can count, for example, the number of distinct substrings. Even more powerful is the suffix automaton, but it awaits you after you own the array confidently.

Task: using the suffix array of banana, count the distinct substrings by hand (the sum of suffix lengths minus the sum of the LCPs; answer: 15). Mark the lesson as completed.