Ordenação por Radix

Utilizando a monotonicidade dos buckets, ordena-se inteiros dígito a dígito do menos significativo para o mais significativo.

Definição de Sufix Array

Para uma string s, define-se sa[i] commo o índice no qual o i-ésimo sufixo (em ordem lexicográfica) começa, e rk[i] como a posição do sufixo que começa em si dentro do sufixo array.

Construção via Método de Duplicação

Seja sa[w][i] o índice do i-ésimo sufixo ao ordenar apenas os primeiros w caracteres de cada sufixo. Para calcular sa[2w] a partir de sa[w], observe que dois sufixos de comprimento 2w podem ser copmarados por dois pares de chaves: os ranks dos blocos de tamanho w. Assim, a ordenação é feita por dois critérios, resultando em complexidade O(n log² n).

const int TAM_MAX = 1e6 + 5;

int comprimento; int sufixo_arr[TAM_MAX * 4], rank_atual[TAM_MAX * 4], rank_temp[TAM_MAX * 4]; std::string texto;

void construir_sa_basico() { std::cin >> texto; comprimento = texto.size(); texto = " " + texto; for (int i = 1; i <= comprimento; ++i) { sufixo_arr[i] = i; rank_atual[i] = texto[i]; } for (int w = 1; w <= comprimento; w <<= 1) { auto comparar = [&](const int a, const int b) { if (rank_atual[a] == rank_atual[b]) return rank_atual[a + w] < rank_atual[b + w]; return rank_atual[a] < rank_atual[b]; }; std::sort(sufixo_arr + 1, sufixo_arr + 1 + comprimento, comparar); int contador = 0; for (int i = 1; i <= comprimento; ++i) rank_temp[sufixo_arr[i]] = (rank_atual[sufixo_arr[i]] == rank_atual[sufixo_arr[i - 1]] && rank_atual[sufixo_arr[i] + w] == rank_atual[sufixo_arr[i - 1] + w]) ? contador : ++contador; for (int i = 1; i <= comprimento; ++i) rank_atual[i] = rank_temp[i]; } for (int i = 1; i <= comprimento; ++i) std::cout << sufixo_arr[i] << ' '; }

</details>Otimização com Radix Sort
-------------------------

Para reduzir a complexidade para *O(n log n)*, utiliza-se ordenação radix em dois passos: primeiro pelo segundo critério, depois pelo primeiro. No entanto, a implementação direta pode ser ineficiente. Uma melhoria é observar que o array `sa` já está parcialmente ordenado, permitindo uma construção mais eficiente ao manipular os ranks diretamente.

<details><summary>Código Otmiizado</summary>```
void construir_sa_otimizado(std::string str, int *suf_arr, int *pos) {
    static int contagem[TAM_MAX], pos_antiga[TAM_MAX * 2], indices[TAM_MAX];
    int n = str.size() - 1;
    std::fill(contagem, contagem + TAM_MAX, 0);
    for (int i = 1; i <= n; ++i) {
        pos[i] = str[i];
        contagem[pos[i]]++;
    }
    for (int i = 1; i <= 128; ++i)
        contagem[i] += contagem[i - 1];
    for (int i = n; i >= 1; --i)
        suf_arr[contagem[pos[i]]--] = i;
    std::copy_n(pos + 1, n, pos_antiga + 1);
    int max_rank = 0;
    for (int i = 1; i <= n; ++i) {
        if (pos_antiga[suf_arr[i]] == pos_antiga[suf_arr[i - 1]])
            pos[suf_arr[i]] = max_rank;
        else
            pos[suf_arr[i]] = ++max_rank;
    }
    for (int w = 1; max_rank < n; w <<= 1) {
        int p = 0;
        for (int i = n - w + 1; i <= n; ++i)
            indices[++p] = i;
        for (int i = 1; i <= n; ++i)
            if (suf_arr[i] > w)
                indices[++p] = suf_arr[i] - w;
        std::fill(contagem + 1, contagem + max_rank + 1, 0);
        for (int i = 1; i <= n; ++i)
            contagem[pos[indices[i]]]++;
        for (int i = 1; i <= max_rank; ++i)
            contagem[i] += contagem[i - 1];
        for (int i = n; i >= 1; --i)
            suf_arr[contagem[pos[indices[i]]]--] = indices[i];
        std::copy_n(pos + 1, n, pos_antiga + 1);
        max_rank = 0;
        for (int i = 1; i <= n; ++i) {
            if (pos_antiga[suf_arr[i]] == pos_antiga[suf_arr[i - 1]] &&
                pos_antiga[suf_arr[i] + w] == pos_antiga[suf_arr[i - 1] + w])
                pos[suf_arr[i]] = max_rank;
            else
                pos[suf_arr[i]] = ++max_rank;
        }
    }
}

Define-se height[i] como o comprimento do prefixo comum mais longo entre os sufixos sa[i-1] e sa[i]. Um lema importante é que height[rk[i]] >= height[rk[i-1]] - 1, o que permite calcular o array em tempo linear.

</details>Aplicações
----------

- O número de substrings distintas de uma string de tamanho *n* é *n(n+1)/2 - Σ height\[i\]* para *i* de 2 a *n*.
- O LCP entre os sufixos `sa[i]` e `sa[j]` é o mínimo de `height[k]` para *k* entre *i+1* e *j*.