Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 - Coggle Diagram
MM11
- 6.6 Suffix Trie/Tree/Array
- 6.6.1 Suffix Trie and Applications
- Definição: sufixo i = substring de i até fim
- Suffix Trie = árvore de todos os sufixos de um conjunto S
- Arestas = caracteres; vértices = path labels
- Bandeiras: termina sufixo? termina palavra?
- Exemplo: S={CAR,CAT,RAT} -> sufixos únicos {AR,AT,CAR,CAT,R,RAT,T}
- Uso principal: dicionário eficiente → busca P em O(m)
- Busca: percorre arestas por caracteres; verifica flag de palavra
- Definição: Suffix Trie com compressão de caminhos (mescla vértices com 1 filho)
- Terminator $ adicionado para garantir folhas
- Arestas podem ter rótulos com múltiplos caracteres
- Propriedade: ≤ 2n vértices (compacto)
- Exemplo: T='GATAGACA$' — relação Trie ↔ Tree (path compression)
- 6.6.3 Aplicações do Suffix Tree
- Objetivo: encontrar todas ocorrências de P em T
- Método: achar vértice x cujo path label = P; ocorrências = índices nas folhas da subárvore de x
-
- Longest Repeated Substring (LRS)
- Resposta = path label do vértice interno mais profundo
-
- Longest Common Substring (LCS) entre T1 e T2
- Construir generalized suffix tree com terminadores diferentes
- Marcar vértices internos que têm folhas de ambas as strings
- Resposta = path label do vértice marcado mais profundo
- Definição: array SA com permutação dos índices [0..n-1] ordenando os sufixos lexicograficamente
- Exemplo: T='GATAGACA$' → SA = {8,7,5,3,1,6,4,0,2}
- Relação com Suffix Tree: ordem das folhas = SA; cada nó interno = intervalo em SA
- Construção ingênua: ordenar sufixos por strcmp → O(n^2 log n)
- Construção eficiente: ordenar por pares de ranks (RA[i], RA[i+k]) para k=1,2,4,... → O(n log n)
- 6.6.5 Aplicações do Suffix Array
- Busca por P usando binary search em SA (lower/upper bound)
-
- LCP (Longest Common Prefix)
- LCP[0]=0; LCP[i] = lcp(suffix SA[i], suffix SA[i-1])
- Calcular via PLCP e Phi em O(n)
- LRS: comprimento = max(LCP)
- LCS (duas strings): concatenar com terminadores distintos; varrer SA/LCP e achar máximo entre sufixos de origens diferentes
- Notas de implementação e observações
- Usar terminadores distintos e ASCII menor
-
-
- Matching: O(m log n) (ou O(m+occ) com Suffix Tree)
- Referências: Manber & Myers; algoritmos de construção SA/LCP (PLCP theorem)
- Fontes principais: A/P Sung Wing Kin, Ken
- Section 6.4: KMP; comparação com strstr/find/indexOf
- Section 6.5: problemas DP não-clássicos
- Section 6.6: Suffix Array (Manber & Myers); usar terminadores; resolver exercícios
- Tópicos adicionais: Hashing, Suffix Automaton, Burrows-Wheeler, Radix Tree
- 6.7 Solution to Non-Starred Exercises & 6.8 Chapter Notes
- 6.7 C Solutions for Section 6.2
- (a) Strings em C: char[] terminado por '\0' (ex.: char str[30*10+50])
- (b) Leitura linha a linha: gets(line) ou fgets(line, 40, stdin)
- (c) Concatenação: strcpy(str, ""); strcat(str, line); adicionar " " entre linhas quando necessário
- (d) Parar: strncmp(line, ".......", 7) == 0
- (a) Procurar substring: p = strstr(str, substr);
- (b) Próximas ocorrências: p = strstr(str + pos, substr)
- Ex 6.2.5: ver solução em C++
- Ex 6.2.6: ler char a char; detectar '\n'; evitar buffer fixo
- 6.7 C++ Solutions for Section 6.2
- Ex 6.2.1: std::string; cin.getline(); concatenar com '+'; comparar com '=='
- Ex 6.2.2: string::find com offset
-
- Ex 6.2.5: map<string,int> para frequências
-
- 6.7 Java Solutions for Section 6.2
- Ex 6.2.1: String / StringBuilder; nextLine / BufferedReader; usar StringBuilder.append; equals()
- Ex 6.2.2: indexOf com offset
- Entender endereços de array C
- Operações char-wise são O(n)
- Funções úteis: tolower/toupper, isalpha/isdigit
- Tokenização: strtok -> vector<string> -> sort