Array de Sufixos

Definição

Seja $s$ uma string de tamanho $n$. O $i$-ésimo sufixo de $s$ é a substring $s[i \ldots n - 1]$.

Uma array de sufixos conterá números inteiros que representam os índices iniciais de todos os sufixos de uma determinada string, após a ordenação desses sufixos.

Como exemplo, veja a string $s = abaab$. Todos os sufixos: $$\begin{array}{ll} 0. & abaab \\ 1. & baab \\ 2. & aab \\ 3. & ab \\ 4. & b \end{array}$$

Após ordenar essas strings: $$\begin{array}{ll} 2. & aab \\ 3. & ab \\ 0. & abaab \\ 4. & b \\ 1. & baab \end{array}$$

Portanto, a array de sufixos para $s$ será $(2,~ 3,~ 0,~ 4,~ 1)$.

Como estrutura de dados, é amplamente utilizada em áreas como compressão de dados, bioinformática e, no geral, em qualquer área que lide com strings e problemas de correspondência de strings.

Construção

abordagem $O(n^2 \log n)$

Essa é uma abordagem mais trivial. Consiga todos os sufixos e ordene-os usando quicksort ou mergesort e, simultaneamente, mantenha seus índices originais. Ordenar custa $O(n \log n)$ comparações, e, como comparar duas strings também levará tempo $O(n)$, obtemos a complexidade final de $O(n^2 \log n)$.

abordagem $O(n \log n)$

A rigor, o algoritmo a seguir não ordena os sufixos, mas as mudanças cíclicas de uma string. No entanto, podemos derivar dele um algoritmo para ordenar sufixos: basta anexar um caractere arbitrário ao final da string, que é menor que qualquer caractere da string. É comum usar o símbolo $\$$. Então, a ordem das mudanças cíclicos ordenadas é equivalente à ordem dos sufixos ordenados, conforme demonstrado aqui com a string $dabbb$.

$$\begin{array}{lll} 1. & abbb\$d & abbb \\ 4. & b\$dabb & b \\ 3. & bb\$dab & bb \\ 2. & bbb\$da & bbb \\ 0. & dabbb\$ & dabbb \end{array}$$

Como vamos ordenar as mudanças cíclicas, consideraremos substrings cíclicas. Usaremos a notação $s[i \dots j]$ para a substring $s$ mesmo que $i > j$. Nesse caso, na verdade queremos dizer a string $s[i \dots n-1] + s[0 \dots j]$. Além disso, pegaremos todos os índices módulo o comprimento de $s$, e omitiremos a operação do módulo por simplicidade.

O algoritmo que discutimos executará $\lceil \log n \rceil + 1$ iterações. Na $k$-ésima iteração ($k = 0 \dots \lceil \log n \rceil$) ordenamos $n$ substrings cíclicas de $s$ de tamanho $2^k$. Depois da $\lceil \log n \rceil$-ésima iteração as substrings de tamanho $2^{\lceil \log n \rceil} \ge n$ portanto isso equivale a ordenar as mudanças cíclicas completamente.

Em cada iteração do algoritmo, além da permutação $p[0 \dots n-1]$, onde $p[i]$ é o índice da $i$-ésima substring (começando de $i$ e com tamanho $2^k$) na ordem ordenada, também manteremos uma array $c[0 \dots n-1]$, onde $c[i]$ corresponde a classe equivalente na qual a substring pertence. Como algumas substrings serão idênticas, o algoritmo precisa tratá-las igualmente. Por conveniência as classes serão números começando de zero. Além disso, os números $c[i]$ erão atribuídos de forma a preservar as informações sobre a ordem: se uma substring for menor que a outra, também deverá ter um rótulo de classe menor. O número de classes equivalentes será armazenado em uma variável $\text{classes}$.

Considere a string $s = aaba$. As substrings cíclicas e as arrays correspondentes $p[]$ e $c[]$ são dadas para cada iteração: $$\begin{array}{cccc} 0: & (a,~ a,~ b,~ a) & p = (0,~ 1,~ 3,~ 2) & c = (0,~ 0,~ 1,~ 0)\\ 1: & (aa,~ ab,~ ba,~ aa) & p = (0,~ 3,~ 1,~ 2) & c = (0,~ 1,~ 2,~ 0)\\ 2: & (aaba,~ abaa,~ baaa,~ aaab) & p = (3,~ 0,~ 1,~ 2) & c = (1,~ 2,~ 3,~ 0)\\ \end{array}$$ Vale a pena notar que os valores de $p[]$ podem ser diferentes. Por exemplo, na $0$ iteração a array também poderia ser $p = (3,~ 1,~ 0,~ 2)$ ou $p = (3,~ 0,~ 1,~ 2)$. Todas essas opções permutam as substrings em uma ordem ordenada. Então elas são todas válidas. Ao mesmo tempo a array $c[]$ é corrigida, não podem haver ambiguidades.

Vamos agora focar na implementação do algoritmo. Escreveremos uma função que pega uma string $s$ e retorna as permutações das mudanças cíclicas ordenadas.

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;

No começo (na "$0$-ésima" iteração) devemos ordenar as substrings cíclicas de comprimento $1$, isto é, devemos ordenar todos os caracteres da string e dividi-los em classes equivalentes (símbolos iguais são atribuídos na mesma classe). Isso pode ser feito trivialmente, por exemplo, usando counting sort. Para cada caractere, contamos quantas vezes ele aparece na string e, em seguida, usamos essas informações para criar a array $p[]$. Depois disso, iremos pela array $p[]$ e construímos $c[]$ comparando caracteres adjacentes.

    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }

Agora temos que falar sobre a etapa da iteração. Vamos supor que já executamos a $k-1$-ésima etapa e calculamos os valores das arrays $p[]$ e $c[]$ para ela. Queremos calcular os valores para a $k$-ésima etapa em tempo $O(n)$. Como executamos esta etapa $O(\log n)$ vezes, o algoritmo completo terá uma complexidade de tempo de $O(n \log n)$.

Para fazer isso, observe que as substrings cíclicas de tamanho $2^k$ consistem de duas substrings de tamanho $2^{k-1}$ que podemos comparar entre si em $O(1)$ usando as informações da fase anterior - os valores da classe equivalente $c[]$. Assim, para duas substrings de comprimento $2^k$ começando da posição $i$ e $j$, todas as informações necessárias para compará-las estão contidas nos pares $(c[i],~ c[i + 2^{k-1}])$ e $(c[j],~ c[j + 2^{k-1}])$. $$\dots \overbrace{ \underbrace{s_i \dots s_{i+2^{k-1}-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[i]} \quad \underbrace{s_{i+2^{k-1}} \dots s_{i+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[i + 2^{k-1}]} }^{\text{length} = 2^k} \dots \overbrace{ \underbrace{s_j \dots s_{j+2^{k-1}-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j]} \quad \underbrace{s_{j+2^{k-1}} \dots s_{j+2^k-1}}_{\text{length} = 2^{k-1},~ \text{class} = c[j + 2^{k-1}]} }^{\text{length} = 2^k} \dots $$

Isso nos dá uma solução bem simples: ordene as substrings de tamanho $2^k$ por esses pares de números. Isso nos dará a ordem requerida $p[]$. No entanto, uma ordenação normal é executada em tempo $O(n \log n)$. Isso nos fornecerá apenas um algoritmo para a construção de uma array de sufixos em $O(n \log^2 n)$.

Como realizamos uma ordenação mais rápida dos pares? Como os elementos dos pares não excedem $n$, podemos usar counting sort de novo. Entretanto, ordenar pares com counting sort não é muito eficiente. Para obter uma constante oculta melhor na complexidade, usaremos outro truque.

Usamos aqui uma técnica na qual o radix sort é baseado: para ordenar os pares, primeiro os ordenamos pelo segundo elemento e depois pelo primeiro elemento (com um stable sort, ou seja, ordenando sem quebrar a ordem relativa dos elementos iguais). No entanto, os segundos elementos já foram ordenados na iteração anterior. Portanto, para ordenar os pares pelos segundos elementos, basta subtrair $2^{k-1}$ do índices em $p[]$ (por exemplo, se a menor substring de comprimento $2^{k-1}$ começa na posição $i$, então a substring de comprimento $2^k$ com a menor segunda metade começa em $i - 2^{k-1}$).

Portanto, apenas por subtrações simples, podemos ordenar os segundos elementos dos pares em $p[]$. Agora precisamos performar um stable sort pelos primeiros elementos. Como já mencionado, isso pode ser alcançado com um 'counting sort'.

A única coisa que resta é calcular as classes de equivalência $c[]$, mas, como antes, isso pode ser feito simplesmente iterando sobre a permutação ordenada $p[]$ e comparando pares vizinhos.

Aqui está a implementação restante. Usamos arrays temporárias $pn[]$ e $cn[]$ para armazenar a permutação pelos segundos elementos e pelos novas classes equivalentes de índices.

    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

O algoritmo requer tempo $O(n \log n)$ e memória $O(n)$. No entanto, se considerarmos o tamanho do alfabeto $k$, ele usará tempo $O((n + k) \log n)$ e memória $O(n + k)$.

Para simplificar, usamos o intervalo ASCII do alfabeto. Se sabemos que a string contém apenas um subconjunto de caracteres, por exemplo, apenas letras minúsculas, essa implementação pode ser otimizada. No entanto, não muito, já que o tamanho do alfabeto aparece apenas com um fator de $O(\log n)$ na complexidade.

Observe também que esse algoritmo ordena apenas as mudanças cíclicas. Conforme mencionado no início desta seção, podemos gerar a ordem ordenada dos sufixos anexando um caractere menor que todos os outros caracteres da string e ordenando essa string resultante por mudanças cíclicas (por exemplo, ordenando as mudanças cíclicas $s + \$$). Isso nos dará a array de sufixos $s$, no entanto precedida por $|s|$.

vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

Aplicações

Encontrar a menor mudança cíclica

O algoritmo acima ordenada todas as mudanças cíclicas (sem anexar um caractere à string) e, portanto $p[0]$ fornece a posição da menor mudança cíclica.

Localizando uma substring em uma string

TA tarefa é encontrar uma string $s$ dentro de um texto $t$, em modo online - conhecemos o texto $t$ antecipadamente, mas não a string $s$. Podemos criar a array de sufixos para o texto $t$ em tempo $O(|t| \log |t|)$. Agora podemos procurar a substring $s$ da seguinte maneira. A ocorrência de $s$ deve ser um prefixo de algum sufixo de $t$. Como ordenamos todos os sufixos, podemos realizar uma pesquisa binária por $s$ em $p$. A comparação do sufixo atual e da substring $s$ na pesquisa binária pode ser feita em tempo $O(|s|)$, portanto, a complexidade para localizar a substring é $O(|s| \log |t|)$. Observe também que, se a substring ocorrer várias vezes em $t$, todas as ocorrências serão próximas umas das outras em $p$. Portanto, o número de ocorrências pode ser encontrado com uma segunda pesquisa binária e todas as ocorrências podem ser impressas.

Comparando duas substrings de uma string

Queremos poder comparar duas substrings de mesmo comprimento de uma determinada string $s$ em tempo $O(1)$, i.e. verificar se a primeira substring é menor que a segunda.

Para isso construímos a array de sufixos em tempo $O(|s| \log |s|)$ e armazenamos todos os resultados intermediários das classes de equivalência $c[]$.

Usando essas informações, podemos comparar quaisquer duas substrings cujo comprimento seja igual a uma potência de dois em O(1): para isso, é suficiente comparar as classes de equivalência de ambas as substrings. Agora queremos generalizar esse método para substrings de comprimento arbitrário.

Vamos comparar duas substrings de comprimento $l$ com os índices iniciais $i$ e $j$. Encontramos o maior comprimento de um bloco que é colocado dentro de uma substring desse comprimento: o maior $k$ de modo que $2^k \le l$. A comparação das duas substrings pode ser substituída pela comparação de dois blocos sobrepostos de comprimento $2^k$: primeiro você precisa comparar os dois blocos começando em $i$ e $j$, e, se forem iguais, compare os dois blocos que terminam em posições $i + l - 1$ e $j + l - 1$: $$\dots \overbrace{\underbrace{s_i \dots s_{i+l-2^k} \dots s_{i+2^k-1}}_{2^k} \dots s_{i+l-1}}^{\text{first}} \dots \overbrace{\underbrace{s_j \dots s_{j+l-2^k} \dots s_{j+2^k-1}}_{2^k} \dots s_{j+l-1}}^{\text{second}} \dots$$ $$\dots \overbrace{s_i \dots \underbrace{s_{i+l-2^k} \dots s_{i+2^k-1} \dots s_{i+l-1}}_{2^k}}^{\text{first}} \dots \overbrace{s_j \dots \underbrace{s_{j+l-2^k} \dots s_{j+2^k-1} \dots s_{j+l-1}}_{2^k}}^{\text{second}} \dots$$

Aqui está a implementação da comparação. Note que é assumido que a função seja chamada com o já calculado $k$. $k$ pode ser calculado com $\lfloor \log l \rfloor$, mas é mais eficiente pré-calcular todos os valores de $k$ para todo $l$. Veja, por exemplo, o artigo sobre a Sparse Table, que usa uma idéia similar e calcula todos os valores de $\log$.

int compare(int i, int j, int l, int k) {
    pair<int, int> a = {c[k][i], c[k][(i+l-(1 << k))%n]};
    pair<int, int> b = {c[k][j], c[k][(j+l-(1 << k))%n]};
    return a == b ? 0 : a < b ? -1 : 1;
}

Maior prefixo comum de duas substrings com memória adicional

Para uma determinada string $s$ queremos calcular o prefixo comum mais longo (LCP) de dois sufixos arbitrários com posição $i$ e $j$.

O método descrito aqui usa $O(|s| \log |s|)$ de memória adicional. Uma abordagem completamente diferente que usará apenas uma quantidade linear de memória é descrita na próxima seção.

Construímos uma array de sufixos em tempo $O(|s| \log |s|)$, e lembramos os resultados intermediários das arrays $c[]$ de cada iteração.

Vamos calcular o LCP para dois sufixos começando em $i$ e $j$. Podemos comparar quaisquer duas substrings com um comprimento igual a uma potência de 2 em $O(1)$. Para fazer isso, comparamos as strings por potência de dois (da maior para a menor) e, se as substrings desse comprimento forem iguais, adicionamos o mesmo comprimento à resposta e continuamos verificando o LCP à direita da parte igual, ou seja, $i$ e $j$ são adicionados pela potência de dois atual.

int lcp(int i, int j) {
    int ans = 0;
    for (int k = log_n; k >= 0; k--) {
        if (c[k][i] == c[k][j]) {
            ans += 1 << k;
            i += 1 << k;
            j += 1 << k;
        }
    }
    return ans;
}

Aqui log_n indica uma constante igual ao logaritmo de $n$ na base $2$ arredondado.

Maior prefixo comum de duas substrings sem memória adicional

Temos a mesma tarefa que na seção anterior. Calculamos o (LCP) para dois sufixos de uma string $s$.

Diferente do método anterior, este usará apenas $O(|s|)$ de memória. O resultado do pré-processamento será uma array (que por si só é uma fonte importante de informações sobre a string e, portanto, também é usada para resolver outras tarefas). As consultas/queries de LCP podem ser respondidas executando consultas de RMQ (consultas de intervalo mínimo/range minimum queries) nessa array, portanto, para diferentes implementações, é possível obter tempo de consulta logarítmico e até constante.

A base desse algoritmo é a seguinte ideia: calcularemos o prefixo comum mais longo para cada par de sufixos adjacentes ordenados. Em outras palavras, construímos uma array $\text{lcp}[0 \dots n-2]$, onde $\text{lcp}[i]$ é igual ao tamanho do prefixo comum mais longo dos sufixos começando em $p[i]$ e $p[i+1]$. Essa array nos dará uma resposta para quaisquer dois sufixos adjacentes da string. Então a resposta para dois sufixos arbitrários, não necessariamente vizinhos, pode ser obtida dessa array. De fato, permita que a solicitação seja calcular o LCP dos sufixos $p[i]$ e $p[j]$. Então, a resposta para esta consulta será $\min(lcp[i],~ lcp[i+1],~ \dots,~ lcp[j-1])$.

Portanto, se tivermos uma array $\text{lcp}$, o problema será reduzido para o RMQ, que possui um grande número de soluções diferentes com diferentes complexidades.

Portanto, a principal tarefa é criar essa array $\text{lcp}$. Usaremos o algoritmo de Kasai, que pode calcular essa array em tempo $O(n)$.

Vejamos dois sufixos adjacentes na ordenados (ordem da array de sufixos). Deixe suas posições iniciais serem $i$ e $j$ e sua $\text{lcp}$ igual a $k > 0$. Se removermos a primeira letra de ambos sufixos - ou seja, pegamos os sufixos $i+1$ e $j+1$ - então o $\text{lcp}$ desses dois será $k - 1$. No entanto, não podemos usar esse valor e escrevê-lo na array $\text{lcp}$, porque esses dois sufixos podem não estar próximos um do outro na ordenação. O sufixo $i+1$ será menor que o sufixo $j+1$, mas pode haver alguns sufixos entre eles. No entanto, como o LCP entre dois sufixos é o valor mínimo de todas as transições, então o LCP entre dois pares nesse intervalo deve ser pelo menos $k-1$, e especialmente também entre $i+1$ e o próximo sufixo. E possivelmente pode ser maior.

Agora já podemos implementar o algoritmo. Iremos iterar sobre os sufixos na ordem de seus comprimentos. Dessa forma, podemos reutilizar o último valor $k$, já que passar do sufixo $i$ para o sufixo $i+1$ é exatamente o mesmo que remover a primeira letra. Será necessário uma array adicional $\text{rank}$, que nos dará a posição de um sufixo na lista ordenada de sufixos.

vector<int> lcp_construction(string const& s, vector<int> const& p) {
    int n = s.size();
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++)
        rank[p[i]] = i;

    int k = 0;
    vector<int> lcp(n-1, 0);
    for (int i = 0; i < n; i++) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = p[rank[i] + 1];
        while (i + k < n && j + k < n && s[i+k] == s[j+k])
            k++;
        lcp[rank[i]] = k;
        if (k)
            k--;
    }
    return lcp;
}

Diminuimos $k$ no máximo $O(n)$ vezes (cada iteração no máximo uma vez, exceto para $\text{rank}[i] == n-1$, onde redefinimos diretamente para $0$), e o LCP entre duas strings é no máximo $n-1$, também aumentaremos $k$ apenas $O(n)$ vezes. Portanto, o algoritmo é executado em tempo $O(n)$.

Número de substrings diferentes

Nós pré-processamos a string $s$ calculando a array de sufixos e a array LCP. Usando essas informações, podemos calcular o número de diferentes substrings na string.

Para fazer isso, vamos pensar sobre quais novas substrings começam na posição $p[0]$, e então em $p[1]$, etc. De fato, conseguimos os sufixos ordenados e vemos quais prefixos fornecem novas substrings. Assim, não vamos esquecer não olhar um por acidente.

Como os sufixos são ordenados, fica claro que o sufixo atual $p[i]$ fornecerá novas substrings para todos os seus prefixos, exceto para os prefixos que coincidam com o sufixo $p[i-1]$. (Assim, todos os prefixos, exceto o primeiro $\text{lcp}[i-1]$). Como o tamanho do sufixo atual é $n - p[i]$, $n - p[i] - \text{lcp}[i-1]$ novos sufixos começam em $p[i]$. Somando todos os sufixos, obtemos a resposta final: $$\sum_{i=0}^{n-1} (n - p[i]) - \sum_{i=0}^{n-2} \text{lcp}[i] = \frac{n^2 + n}{2} - \sum_{i=0}^{n-2} \text{lcp}[i]$$

Problemas