Please enable JavaScript.
Coggle requires JavaScript to display documents.
6.6 Suffix Trie / Tree / Array - Coggle Diagram
6.6 Suffix Trie / Tree / Array
6.6.1 Suffix Trie
Trie contendo todos os sufixos de S
Simples, porém pode ter O(n²) espaço
Usado para dictionary matching: busca P em O(m)
Não é eficiente para strings muito longas
6.6.2 Suffix Tree
Suffix Trie comprimida → O(n) espaço
Cada sufixo termina em um leaf
Internal nodes = prefixos comuns de >1 sufixo
Aplicações:
String matching: O(m + occ)
Longest Repeated Substring: nó interno mais profundo
Longest Common Substring entre 2 strings:
Construir Suffix Tree generalizado
6.6.3 Aplicações do Suffix Tree
Matching muito rápido
LRS em O(n)
LCS para 2+ strings marcando folhas de origem
6.6.4 Suffix Array
Vetor de sufixos ordenados lexicograficamente
Alternativa mais simples ao Suffix Tree
Construção:
Método naive: O(n² log n)
Método Manber & Myers: O(n log n)
Estruturas:
SA = sufixos ordenados
RA = ranks dos prefixos
Iterações: 1, 2, 4, 8...
6.6.5 Aplicações do Suffix Array
String Matching:
Binary search nos sufixos → O(m log n)
LCP (Longest Common Prefix):
Ingênuo: O(n²)
PLCP + Phi: O(n)
Longest Repeated Substring:
Max(LCP)
Longest Common Substring:
Construir SA de T1#T2 e verificar LCP entre donos diferentes