Introdução ao Autômato Sufixo

Para uma cadeia de caracteres de comprimento n, o número de subcadeias é O(n²), o que limita significativamente o estudo de problemas relacionados a subcadeias. O DAWG (Grafo Acíclico Dirigido de Palavras) surgiu para resolver essa limitação, representando todas as subcadeias usando O(n) estados e sendo construído incrementalmente em tempo linear. O Autômato Sufixo (SAM) é um tipo de DAWG cujos estados de aceitação são todos os sufixos da cadeia s.

De forma intuitiva, o SAM é uma versão compacta de todas as subcadeias de uma dada cadeia. Um SAM possui no máximo 2n - 1 nós e 3n - 4 transições.

Conjunto endpos

Definição

O conjunto de todas as posições finais de ocorrência de uma subcadeia t dentro de s é denotado por endpos(t). Por exemplo, se s = "abbab" e t = "ab", então endpos(t) = {2, 5}.

Duas subcadeias t₁ e t₂ pertencem à mesma classe de equivalência de endpos se endpos(t₁) = endpos(t₂). Essas classes formam os estados do SAM.

Propriedades

• Se t₁ e t₂ pertencem à mesma classe (com |t₁| ≤ |t₂|), então t₁ é sufixo de t₂.
• Para quaisquer duas subcadeias t₁ e t₂ (com |t₁| ≤ |t₂|), vale endpos(t₁) ⊇ endpos(t₂) ou endpos(t₁) ∩ endpos(t₂) = ∅.
• Os comprimentos das subcadeias em uma mesma classe de equivalência são contínuos.
• O número de classes de equivalência é O(n).

Árvore de Links (Parent Tree)

Entroduzimos as notações:

• longest(i): a subcadeia mais longa na classe i.
• len(i): comprimento de longest(i).
• shortest(i): a subcadeia mais curta na classe i.
• minlen(i): comprimento de shortest(i).

A relação de partição dos conjuntos endpos forma uma árvore chamada Árvore de Links (ou Parent Tree). O pai de um nó i é denotado por link(i), conhecido como link de sufixo. Tem-se que minlen(i) = len(link(i)) + 1.

Construção do SAM

Estados e Transições

No SAM, cada classe de equivalência corresponde a um estado. A função de transição δ(x, c) indica a transição a partir do estado x ao adicionar o caractere c ao final da cadeia atual.

Algoritmo de Inserção

O código a seguir demonstra a inserção de um caractere no SAM:

void Inserir(int c) {
    int p = ultimo;
    int q = ultimo = ++contador;
    tamanho[q] = tamanho[p] + 1;
    for (; p && !trans[p][c]; p = link[p]) {
        trans[p][c] = q;
    }
    if (!p) {
        link[q] = 1;
        return;
    }
    int np = trans[p][c];
    if (tamanho[np] == tamanho[p] + 1) {
        link[q] = np;
        return;
    }
    int nq = ++contador;
    memcpy(trans[nq], trans[np], sizeof(trans[nq]));
    link[nq] = link[np];
    link[np] = link[q] = nq;
    tamanho[nq] = tamanho[p] + 1;
    for (; p && trans[p][c] == np; p = link[p]) {
        trans[p][c] = nq;
    }
}

A variável ultimo mantém o último nó inserido, trans[p][c] armazena δ(p, c), e link corresponde ao link de sufixo. O algoritmo mantém apenas δ, link e len, pois outras informações como o tamanho do endpos podem ser calculadas depois ou afetariam a complexidade.

Propriedades e Template Básico

• Para uma cadeia de comprimento n, o SAM possui no máximo 2n - 1 estados e 3n - 4 transições.
• Marcar todos os caracteres percorrendo os links de sufixo de forma bruta resulta em O(n√n) operações.

Template do SAM com consulta para a maior subcadeia repetida:

struct AutomatoSufixo {
    int tamanho[N<<1], trans[N<<1][M], link[N<<1], contagem[N<<1];
    int ultimo = 1, contador = 1;
    
    void Inserir(int c) {
        // ... (código similar ao anterior, adaptado)
    }
    
    long long Consultar() {
        long long resposta = 0;
        for (int i = 1; i <= contador; i++) {
            // ... (código de processamento)
        }
        return resposta;
    }
};

Técnicas Comuns

Alfabeto Grande

Para alfabetos grandes, utilize um map para as transições, com complexidade O(n log |Σ|).

Ordem Topológica

Como o SAM é um DAG, podemos ordenar os estados por len usando um balde (bucket sort):

for (int i = 1; i <= contador; i++) ++balde[tamanho[i]];
for (int i = 1; i <= n; i++) balde[i] += balde[i-1];
for (int i = 1; i <= contador; i++) ordem[balde[tamanho[i]]--] = i;

Calcular Tamanho do endpos

Seja contagem(i) = |endpos(i)|. Para classes sem perda, tem-se contagem(i) = Σ contagem(j) para todo j com link(j) = i. As folhas (prefixos da cadeia original) são inicializadas com contagem = 1. Em seguida, soma-se os valores na Árvore de Links.

Técnicas Clássicas

Contar Subcadeias Distintas

O número de subcadeias distintas é:

ans = Σ (tamanho[u] - tamanho[link[u]])

long long ConsultarSubcadeiasDistintas() {
    long long ans = 0;
    for (int i = 1; i <= contador; i++) {
        ans += tamanho[i] - tamanho[link[i]];
    }
    return ans;
}

k-ésima Menor Subcadeia

Calcule o número de subcadeias a partir de cada estado. Em seguida, percorra as transições de 'a' a 'z', acumulando até encontrar a transição correspondente à posição k.

Ocorrências Dinâmicas

Para consultas a subcadeias Tᵢ em uma cadeia texto S, pode-se construir o SAM de S e, para cada consulta, percorrer o autômato. O número de ocorrências de Tᵢ é o tamanho do endpos do estado final, calculável com uma DFS na Árvore de Links.

Longest Common Substring (LCS) Dinâmico

Ao adicionar caracteres dinamicamente, a Árvore de Links preserva uma árvore virtual, permitindo o cálculo do LCS através do LCA (Lowest Common Ancestor).

Autômato Sufixo Generalizado (GSA)

Para múltiplas cadeias, utiliza-se o Autômato Sufixo Generalizado. Existem três abordagens:

1. Concatenar as cadeias com separadores e construir o SAM.
2. Construir uma Trie e, por BFS, construir o SAM (offline).
3. Para cada cadeia, construir a partir da raiz do SAM, com tratamento especial para evitar estados desnecessários (online).

Construção Offline via BFS

void ConstruirGSA() {
    queue<int> fila;
    // Inserir primeira camada de caracteres
    pos[1] = 1;
    while (!fila.empty()) {
        int u = fila.front(); fila.pop();
        pos[u] = Inserir(caractere[u], pos[pai[u]]);
        // Enfileirar filhos
    }
}</int>

Construção Online com Tratamento

No início de Inserir, adicione:

if (trans[ultimo][c]) {
    // Verificar e reutilizar estado existente ou dividir
    // ...
    return estado_existente;
}

Isso garante que inserções repetidas não criem estados redundantes.

Fundamentos de Autômatos

Um AFD (Autômato Finito Determinístico) é uma 5-tupla (Q, Σ, δ, q₀, F), onde Q é o conjunto de estados, Σ o alfabeto, δ a função de transição, q₀ o estado inicial e F o conjunto de estados finais.

Um AFN (Autômato Finito Não Determinístico) difere por sua função de transição retornar um conjunto de estados.

O DAWG aceita todas as subcadeias de uma palavra com O(n) estados, sendo o SAM um caso especial deste.