O autômato de sufixos (SAM) e sua árvore de pais compartilham os mesmos nós, mas possuem semânticas distintas: - Cada nó representa uma classe de equivalência de endpos — o conjunto de posições finais de todas as ocorrências de uma substring. - A árvore de pais é uma estrutura hierárquica em forma de árvore, onde a aresta do pai para o filho corresponde à adição de um caractere à esquerda (ou seja, extensão do prefixo). - O SAM propriamente dito é um grafo acíclico dirigido (DAG), onde uma aresta do nó u para v com rótulo c significa que a substring representada por v é obtida ao concatenar c ao final da substring representada por u. Uma propriedade central: cada caminho no SAM, partindo da raiz, corresponde univocamente a uma substring distinta da cadeia original, e o nó de destino codifica exatamente o conjunto de posições finais dessa substring. Na implementação típica: - fa[u] armazena o pai de u na árvore de pais; - ch[u][c] aponta para o sucessor no SAM ao ler o caractere c. ### 2. Significado e Propriedades do Conjunto endpos

Para qualquer substring s, endpos(s) é o conjunto de índices i tais que s ocorre terminando na posição i da string. A cardinalidade |endpos(u)|, denotada como f[u], indica quantas vezes as substrings associadas ao nó u aparecem. Na árvore de pais: - f[u] = 1 + Σ f[v], onde v percorre os filhos diretos de u, exceto quando u representa um prefixo — nesse caso, há exatamente uma posição final ("perdida") que não aparece em nenhum dos filhos. - Todo endpos(v) está contido em endpos(u) se v for filho de u. Essa "perda" ocorre exclusivamente em nós que representam prefixos — pois não é possível estender à esquerda um prefixo sem sair do domínio das substrings da string original. Assim, todos os nós folha da árvore de pais correspondem a prefixos. ### 3. Atributo len: Comprimento das Substrings Representadas

Conhecer apenas as posições finais não determina a substring — precisamos também do comprimento. Por isso, cada nó u armazena len[u]: o comprimento máximo entre todas as substrings em sua classe de equivalência. Propriedades-chave: - Na árvore de pais, o menor comprimento representado por u é len[fa[u]] + 1. - No SAM, se ch[u][c] == v, então len[v] ≥ len[u] + 1. Isso decorre do fato de que toda substring em u pode ser estendida por c; como v pode ter múltiplos pais no DAG, seu len é definido pelo maior desses valores possíveis. Justificativa para len[fa[u]] + 1 ser o mínimo: suponha que exista uma substring s em u com |s| < len[fa[u]] + 1. Então s também pertenceria à classe de fa[u], contradizendo a maximalidade de len[fa[u]]. ### 4. Construção Incremental do SAM

A construção processa a string caractere a caractere, mantendo invariantes estruturais do SAM. A raiz (node 1) representa a string vazia (len[1] = 0). Seja lst o nó correspondente ao sufixo completo até a posição anterior ([0..i−1]). Ao inserir o novo caractere c na posição i: 1. Novo nó básico: cria-se now, com len[now] = len[lst] + 1. Esse nó represanta o sufixo completo [0..i]. 2. Propagação para cima na árvore de pais: partindo de lst, sobe-se via fa até encontrar o primeiro nó p tal que ch[p][c] já esteja definido (ou até a raiz). 3. Caso 1 — Sem divisão: se p não existe (p == 0), então fa[now] = 1. Isso implica que c é inédito na string até agora. 4. Caso 2 — Fusão direta: se q = ch[p][c] satisfaz len[q] == len[p] + 1, então q já captura exatamente todas as extensões válidas de p com c; basta definir fa[now] = q. 5. Caso 3 — Divisão de nó: caso contrário, q contém substrings mais longas cujo endpos ainda não inclui i. Cria-se um clone nq com: - len[nq] = len[p] + 1, - ch[nq] = ch[q], - fa[nq] = fa[q], seguido de fa[q] = fa[now] = nq.

 Em seguida, retrocede-se por `p = fa[p]`, reatribuindo `ch[p][c] = nq` enquanto `ch[p][c] == q`.

A divisão garante que a propriedade de equivalência de endpos seja preservada: nq herda exatamente as substrings de q com comprimento ≤ len[p]+1, agora atualizadas com a nova posição final i. ### 5. Computação Eficiente de f[u] = |endpos(u)|

Como apenas os nós que representam prefixos têm contribuição "não herdada" para endpos, inicializamos f[u] = 1 para todo nó criado durante a inserção de um novo sufixo completo (i.e., todos os nós now gerados). Em seguida, realizamos uma DFS pós-ordem na árvore de pais, acumulando: ``` f[fa[u]] += f[u];

O valor final em `f[u]` é exatamente a cardinalidade do conjunto *endpos* do nó `u`. </div>