Что такое массив LCP и как построить его за O(n) алгоритмом Касаи?

lcp[i] = длина наибольшего общего префикса суффиксов sa[i-1] и sa[i] (соседних в отсортированном порядке). Касаи использует ключевое наблюдение: если суффикс с позиции i имеет с соседом LCP = h, то суффикс с позиции i+1 имеет LCP с СВОИМ соседом не меньше h-1. Значит, переходя по суффиксам в порядке исходных позиций, можно только уменьшать h на 1 и доращивать — суммарно O(n) сравнений.

vector<int> build_lcp(const string& s, const vector<int>& sa) {
    int n = s.size();
    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) {
            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;            // ключевая строка: переносим h-1 дальше
        } else h = 0;
    }
    return lcp;
}

Линейность: h суммарно увеличивается не более чем на n (каждый ++h сдвигает совпавший префикс), а уменьшается не больше n раз (по разу на итерацию). Итог — O(n) время, O(n) память. Именно строка --h обеспечивает амортизацию.