Depois de um pouco de leitura, descobri o que um array de sufixos e um array de LCP representa.

Matriz de sufixo: Representa a classificação _lexicográfica de cada sufixo de uma matriz.

Matriz de LCP : Contém a correspondência de prefixo de comprimento máximo entre dois sufixos consecutivos, depois que eles sãoclassificado lexicograficamente.

Eu tenho tentado muito entender desde alguns dias, como exatamente oO array de sufixos e o algoritmo LCP funcionam.

Aqui está o código, que é retiradoCodeforces:

/*
Suffix array O(n lg^2 n)
LCP table O(n)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

namespace SuffixArray
{
    const int MAXN = 1 << 21;
    char * S;
    int N, gap;
    int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

    bool sufCmp(int i, int j)
    {
        if (pos[i] != pos[j])
            return pos[i] < pos[j];
        i += gap;
        j += gap;
        return (i < N && j < N) ? pos[i] < pos[j] : i > j;
    }

    void buildSA()
    {
        N = strlen(S);
        REP(i, N) sa[i] = i, pos[i] = S[i];
        for (gap = 1;; gap *= 2)
        {
            sort(sa, sa + N, sufCmp);
            REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
            REP(i, N) pos[sa[i]] = tmp[i];
            if (tmp[N - 1] == N - 1) break;
        }
    }

    void buildLCP()
    {
        for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
        {
            for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
            ++k;
            lcp[pos[i]] = k;
            if (k)--k;
        }
    }
} // end namespace SuffixArray

Eu não posso, simplesmente não consigo entender como esse algoritmo funciona. Eu tentei trabalhar em um exemplo usando lápis e papel, e escrevi através dos passos envolvidos, mas perdi a ligação entre eles, pois é muito complicado, pelo menos para mim.

Qualquer ajuda sobre explicação, usando um exemplo talvez, é muito apreciada.