§1  ANAGRAMAS  INTRODUCAO 1

October 18, 1999 at 08:13

1. Introducao. Este programa resolve um problema proposto pelos professores Imre Simon e Paulo Feofiloff em MAC122. Resolvi escrever este programa porque gostei do problema e achei que poderia me divertir em meu tempo livre escrevendo este programa. (Tempo livre? Que tempo livre?) A solução que implementei está além do escopo de MAC122; acredito entretanto que pode ser estimulante para os alunos desta disciplina ver uma solução usando uma estrutura de dados muito interessante, chamada treaps. Com um pouco de sorte, esta estrutura será discutida na disciplina MAC323, Estruturas de Dados.

Este programa, na verdade, deve ser fácil para eu escrever, pois estou basicamente apenas modificando um programa já pronto, devido a Knuth, a saber, o wordtest, escrito em CWEB. O CWEB é um sistema de programação baseado na filosofia de Programação Literária (Literate Programming).

2. O problema proposto é o seguinte. É dado um arquivo de palavras, com uma palavra por linha. Vamos admitir que todas as palavras deste arquivo são distintas. (Usando sort e uniq, podemos sempre eliminar palavras repetidas.) Dizemos que duas palavras são equivalentes se uma for anagrama da outra. Deseja-se encontrar um subconjunto das palavras do arquivo dado que sejam todas equivalentes entre si; ademais, queremos um tal subconjunto de maior peso possível, onde o peso de um conjunto de palavras é o número total de letras neste conjunto. Note que a relação de ser anagrama é uma relação de equivalência, de forma que estamos à procura de uma classe de equivalência de peso maior possível; em outras palavras, queremos maximizar o produto lm, onde l é o comprimento comum das palavras na classe de equivalência e m é o número de elementos nesta classe de equivalência.

Este programa recebe no stdin o arquivo dado e devolve em stdout um subconjunto de palavras equivalentes de peso máximo. Assumimos que todas as palavras de stdin terminam com .

3. A idéia básica que usaremos é a seguinte. Associamos a cada palavra s uma forma canônica, a saber, a palavra t que têm exatamente as mesmas letras de s, mas em ordem alfabética (de acordo com o código ASCII dos caracteres). Por exemplo, se s é a palavra “abóbora”, a forma canônica de s é a palavra “aabboró” (bem, não sei se chamar esta palavra de “palavra” faz sentido). Então, duas palavras são equivalentes se e só se elas têm a mesma forma canônica.

4. Supomos que as palavras tem no máximo caracteres.

#define  50

2  INTRODUCAO  ANAGRAMAS §5

5. A organização deste programa é a típica de programas em C. Se erros são detectados, uma mensagem é enviada para stderr e um valor não nulo é devolvido. O usuário pode escolher entre duas opções. Ele pode pedir que o programa envie para stdout as palavras de uma classe de equivalência de maior peso (este é o comportamento default), ou ele pode especificar a opção -nN, onde N é um inteiro. Com esta opção, este programa determina os n maiores inteiros w para os quais existem classes de equivalência de peso w e imprime todas estas classes de equivalência. Desta forma, o comportamento deste programa quando ele é chamado sem opção nenhuma é basicamente o mesmo daquele quando ele é chamado com a opção -n1. #include #include

⟨ Typedefs 7 ⟩ int main(int argc, char ∗argv [ ]) {

⟨ Variáveis locais 8 ⟩;

⟨ Interprete a linha de comando 6 ⟩;

⟨ Processe a lista de palavras 18 ⟩;

if (n pesos ) ⟨ Imprima as classes cujos pesos são os n pesos maiores pesos 27 ⟩ else ⟨ Encontre uma classe de equivalência de peso máximo e imprima 24 ⟩ return 0;

}

6. ⟨ Interprete a linha de comando 6 ⟩ ≡

while (^{−}argc) { if (sscanf (argv [argc], , &n pesos ) ≡ 1) ; else {

fprintf (stderr , ␣ ␣ , argv [0]); return −6;

} }

This code is used in section 5.

7. Usaremos o tipo byte para os caracteres. As palavras de uma classe de equivalência serão colocadas em uma lista ligada, cujas células serão do tipo cell . ⟨ Typedefs 7 ⟩ ≡

typedef unsigned char byte; /∗ um byte varia de 0 a 255 ∗/ typedef struct list node ∗link; typedef struct list node {

byte ∗w;

link next ; } cell; /∗ célula das listas ligadas de palavras ∗/

See also section 9. This code is used in section 5.

8. ⟨ Variáveis locais 8 ⟩ ≡ unsigned max length = ; /∗ comprimento máximo de uma palavra ∗/ register long c; /∗ índice genérico ∗/ register byte ∗u, ∗v; /∗ ponteiros para caracteres de strings sendo processados no momento ∗/ long n pesos = 0; /∗ imprimimos as classes cujos pesos estão dentre os n pesos maiores pesos ∗/ long N classes = 0; /∗ número de classes encontradas ∗/

See also sections 11, 16, and 17. This code is used in section 5.

§9  ANAGRAMAS  TREAPS 3

9. Treaps. A parte mais interessante deste programa é a estrutura de dados que é utilizada para se manter uma tabela de símbolos. Usaremos a estrutura de “treap” de Aragon e Seidel [30th IEEE Symposium on Foundations of Computer Science (1989), 540–546]. Um treap é uma árvore binária cujos nós têm duas chaves. Os nós da árvore vão corresponder às classes de equivalências das palavras da lista de palavras dadas. A chave primária de um nó, que em nossa aplicação será a forma canônica naturalmente associada à classe de equivalência deste nó, obedece a condição de árvore de busca binária: o filho esquerdo de um nó p e todos os seus descendentes têm chave primária menor que a chave primária de p, e o filho direito de p e todos os seus descendentes têm chave primária maior que a chave primária de p. A chave secundária, que em nossa aplicação será um número pseudoaleatório associado ao nó em questão, obedece a propriedade de heap: a chave secundária de todos os descendentes de um nó p têm chave secundária maior que a chave secundária de p.

Um dado conjunto de nós com chaves primárias e secundárais todas distintas pode ser organizado em um treap de forma única. Este treap pode ser obtido, por exemplo, usando-se o procedimento padrão de inserção em árvore binária: basta se inserir os nós em ordem crescente da chave secundária. Daí segue que se as chaves secundárias forem aleatórias, a árvore será balanceada com alta probabilidade.

As chaves secundárias serão unsigned long, e o valor atribuído ao n-ésimo nó será (cn) mod 2^{32}, onde c é um número ímpar. Isto vai garantir que as chaves secundárias sejam todas distintas. Escolhendo c próximo a (cn) mod 2^{32}, onde ϕ é a razão áurea (1 + \sqrt{5} )/2, teremos, muito provavelmente, uma distribuição aleatória o suficiente em relação aos dados de entrada. Para uma discussão deste fato, veja o volume 3 do TAOCP de Knuth [The Art of Computer Programming, Sorting and Searching (seção sobre hashing)].

Em nosso treap, cada classe de equivalência corresponde a um nó. Este nó contém um campo m que registra o número corrente de elementos nesta classe de equivalência; temos também o campo l que contém o comprimento comum das palavras desta classe. Ademais, um campo h aponta para o primeiro elemento de uma lista ligada que contém as palavras desta classe de equivalência. #define 2654435769 /∗ ≈ 2^{32}/ϕ ∗/ ⟨ Typedefs 7 ⟩ +≡

typedef struct node struct { struct node struct ∗left , ∗right ; /∗ filhos ∗/ byte ∗keyword ; /∗ chave primária ∗/ unsigned long rank ; /∗ chave secundária ∗/ long m; /∗ número de palavras na classe de equivalência ∗/ long l; /∗ comprimento das palavras desta classe de equivalência ∗/ link h; /∗ início da lista de palavras da classe de equivalência ∗/

4  TREAPS  ANAGRAMAS §10

} node; /∗ nó do treap ∗/ 10. Nesta implementação, quando descobrimos que queremos inserir um novo nó no treap, refazemos a busca (sem sucesso) para determinar o local da árvore onde devemos fazer a inserção. Este processo é um pouco mais demorado que o processo de busca simples, no qual queremos apenas determinar a presença ou não de um elemento no treap. Naturalmente, ao invés de adotarmos a estratégia que escolhemos (busca simples e repetição de trabalho quando precisamos executar uma inserção), poderíamos executar este processo de busca um pouco mais complicado sempre, para evitar esta repetição de trabalho no caso em que inserção é necessária. Não é claro qual das duas estratégias é melhor em geral. Isto depende, naturalmente, da proporção de buscas sem sucesso que esperamos com as nossas entradas.

No problema que queremos resolver, muito provavelmente o número de buscas sem sucesso é muito grande, e portanto a estratégia alternativa (aquela não utilizada neste programa) deve ser a mais eficiente! Fica como exercício para o leitor alterar este programa e verificar experimentalmente o ganho de eficiência. Um argumento heurístico sugere que o ganho deve ser substancial.

O processo de inserção de uma nova classe de equivalência (isto é, um novo nó) em nosso treap é parecido com o processo de busca. Percorremos o treap até encontrarmos um nó cuja chave secundária é maior que a do nó a ser inserido. Inserimos então o novo nó nesta posição, e partimos o nó antigo e seus descendentes em duas subárvores que se tornarão as subárvores esquerda e direita do nó recém-inserido. ⟨ Insira o nó correspondente a buffer no treap 10 ⟩ ≡

{ register node ∗p, ∗∗q, ∗∗qq , ∗r; current rank += ; /∗ soma (unsigned) mod 2^{32} ∗/ p = root ; q = &root ; while (p) {

if (p rank > current rank ) break; /∗ fim da primeira fase ∗/ for (u = buffer , v = p keyword ; ∗u ≡ ∗v; u^{++}, v^{++}) ; if (∗u < ∗v) q = &(p left ), p = ∗q; else q = &(p right ), p = ∗q;

}

⟨ Faça r apontar para um novo nó e ponha buffer neste nó 13 ⟩; r rank = current rank ; ∗q = r; /∗ adicionamos o novo nó na árvore ∗/ N classes^{++}; ⟨ Quebre a subárvore p e pendure as duas árvores resultantes em r 12 ⟩;

}

This code is used in section 18.

11. ⟨ Variáveis locais 8 ⟩ +≡ unsigned long current rank = 0; /∗ número pseudoaleatório ∗/ 12. Neste ponto a árvore p pode já estar vazia. Caso contrário, executamos um procedimento de partição nesta árvore e penduramos as duas árvores resultantes em r. O fato de que este processo de partição resulta em um treap é não trivial, e fica como exercício para o leitor. ⟨ Quebre a subárvore p e pendure as duas árvores resultantes em r 12 ⟩ ≡

q = &(r left ); qq = &(r right ); /∗ ponteiros a serem determinados durante o processo ∗/ while (p) {

for (u = buffer , v = p keyword ; ∗u ≡ ∗v; u^{++}, v^{++}) ;

if (∗u < ∗v) {

∗qq = p;
qq = &(p left );
p = ∗qq ;

} else {

∗q = p;
q = &(p right );
p = ∗q;

} } ∗q = ∗qq = Λ;

This code is used in section 10.

13. Alocamos memória para os nós de nossa árvore dinamicamente, 500 nós por vez, para evitar chamadas frequentes ao sistema. Analogamente, alocamos memória dinamicamente para as células de nossas listas ligadas, 500 células por vez. Também alocamos memória para os nossos strings dinamicamente, 5000 caracteres por vez (além do necessário para uso imediato). Usaremos a variável l para guardar o comprimento da palavra em buffer .

#define  500
#define  500
#define  5000

#define out of mem(x)

{ fprintf (stderr , ␣ ␣ , ∗argv );

return x; }

⟨ Faça r apontar para um novo nó e ponha buffer neste nó 13 ⟩ ≡

if (next node ≡ bad node) { next node = (node ∗) calloc( , sizeof (node)); if (next node ≡ Λ) out of mem(−2); bad node = next node + ;

}

r = next node^{++};

⟨ Copie buffer na memória alocada para strings e faça r keyword apontar para esta cópia 14 ⟩; ⟨ Insira palavra corrente na lista de r 15 ⟩;

This code is used in section 10.

14. ⟨ Copie buffer na memória alocada para strings e faça r keyword apontar para esta cópia 14 ⟩ ≡

if (next string + l + 1 ≥ bad string ) { int block size = + l + 1; next string = (byte ∗) malloc(block size); if (next string ≡ Λ) out of mem(−3); bad string = next string + block size;

} r keyword = next string ; for (u = buffer , v = next string ; ∗u ≠ ; u^{++}, v^{++}) ∗v = ∗u; ∗v = ; next string = v + 1;

This code is used in section 13.

15. ⟨ Insira palavra corrente na lista de r 15 ⟩ ≡

{ register link p;

if (next cell ≡ bad cell ) { next cell = (cell ∗) calloc( , sizeof (cell)); if (next cell ≡ Λ) out of mem(−4); bad cell = next cell + ;

}

p = next cell^{++};

p w = palavra corrente;

p next = Λ;

r h = p;

r m = 1;

r l = l; }

This code is used in section 13.

16. Declaramos aqui as variáveis que temos usado nas rotinas de alocação de memória. ⟨ Variáveis locais 8 ⟩ +≡

node ∗next node = Λ, ∗bad node = Λ; cell ∗next cell = Λ, ∗bad cell = Λ; byte ∗next string = Λ, ∗bad string = Λ; node ∗root = Λ; byte ∗buffer ; byte ∗palavra corrente; long l; /∗ comprimento da palavra em buffer ∗/

17. Ao terminarmos uma busca com sucesso em nosso treap, teremos anagrama ≡ 1 e loco encontrado será o nó do treap onde encontramos a palavra procurada. ⟨ Variáveis locais 8 ⟩ +≡

node ∗loco encontrado = Λ; long anagrama = 0; 18. Os mecanismos de busca e inserção em nosso treap já estão quase todos prontos; devemos apenas executá-los nos momentos apropriados. ⟨ Processe a lista de palavras 18 ⟩ ≡

buffer = (byte ∗) malloc(max length + 1); if (buffer ≡ Λ) out of mem(−5); while (1) {

⟨ Leia em buffer a próxima palavra em stdin; goto done caso o arquivo terminou 23 ⟩; ⟨ Faça uma cópia de buffer na memória alocada para strings e canonize buffer “in loco” 21 ⟩; if (l) {

⟨ Procure buffer no treap 19 ⟩;

if (anagrama) ⟨ Insira palavra corrente na lista do loco encontrado 20 ⟩ else ⟨ Insira o nó correspondente a buffer no treap 10 ⟩;

} }

done: ;

This code is used in section 5.

19. Implementamos abaixo a nossa própria versão de strcmp( ), que é usada para a comparação da forma canônica da palavra lida de stdin e da chave primária de um nó do treap. Supomos que a forma canônica está em buffer , terminada por , e que as chaves primárias terminam com . Fazemos acesso ao treap através de root , um ponteiro para a sua raiz. ⟨ Procure buffer no treap 19 ⟩ ≡

{ register node ∗p = root ;

while (p) { for (u = buffer , v = p keyword ; ∗u ≡ ∗v; u^{++}, v^{++}) ; if (∗v ≡ ∧ ∗u ≡ ) {

anagrama = 1;

loco encontrado = p; break;

}

if (∗u < ∗v) p = p left ;

else p = p right ; }

}

This code is used in section 18.

20. ⟨ Insira palavra corrente na lista do loco encontrado 20 ⟩ ≡

{ register link p;

if (next cell ≡ bad cell ) { next cell = (cell ∗) calloc( , sizeof (cell)); if (next cell ≡ Λ) out of mem(−4); bad cell = next cell + ;

} p = next cell^{++}; p w = palavra corrente; p next = loco encontrado h; loco encontrado h = p; loco encontrado m^{++};

}

This code is used in section 18.

21. ⟨ Faça uma cópia de buffer na memória alocada para strings e canonize buffer “in loco” 21 ⟩ ≡

{

if (next string + l + 1 ≥ bad string ) { int block size = + l + 1; next string = (byte ∗) malloc(block size); if (next string ≡ Λ) out of mem(−3); bad string = next string + block size;

} palavra corrente = next string ; for (u = buffer , v = next string ; ∗u ≠ ; u^{++}, v^{++}) ∗v = ∗u; ∗v = ; next string = v + 1; ⟨ Canonize buffer 22 ⟩;

}

This code is used in section 18.

22. Usamos aqui o insertion sort. ⟨ Canonize buffer 22 ⟩ ≡

{ register byte ∗p, ∗q; register byte b; for (p = buffer + 1; p < buffer + l; p^{++})

for (q = p; q > buffer ; q^{−})

if (∗(q − 1) < ∗q) break;

else {

b = ∗(q − 1);
∗(q − 1) = ∗q;
∗q = b;

} }

This code is used in section 21.

23. ⟨ Leia em buffer a próxima palavra em stdin; goto done caso o arquivo terminou 23 ⟩ ≡ u = buffer ; l = 0; anagrama = 0; while (l < max length) {

c = getchar ( ); if (c ≡ ) {

if (ferror (stdin)) { fprintf (stderr , ␣ ␣ ␣ ␣ ␣ , ∗argv ); return −6;

}

goto done; /∗ fim de arquivo; a palavra corrente, se houver uma, é ignorada ∗/ } if (c ≡ ) break; else {

∗u^{++} = (byte) c;

l^{++}; }

} ∗u = ;

This code is used in section 18.

24. Após termos processado todas as palavras da entrada, percorreremos o nosso treap e montaremos uma lista ligada com os nós desta árvore. Ao fazermos isto, destruiremos o nosso treap. Nest fase, root vai apontar para uma pilha de nós que ainda devem ser visitados (cada visita destas seguida da visita a toda a subárvore direita de cada um destes nós). ⟨ Encontre uma classe de equivalência de peso máximo e imprima 24 ⟩ ≡

{ register node ∗p max = Λ; register long pp = 0; if (root ≠ Λ) { register node ∗p, ∗q;

p = root ; root = Λ; while (1) {

while (p left ≠ Λ) { q = p left ; p left = root ; /∗ usamos left para implementarmos a pilha ∗/ root = p; p = q;

} visit : ⟨ Verifique o peso de p e atualize o máximo caso necessário 25 ⟩

if (p right ≡ Λ) { if (root ≡ Λ) break; /∗ a pilha está vazia; terminamos ∗/ p = root ; root = root left ; /∗ desempilha! ∗/ goto visit ;

}

else p = p right ; } } ⟨ Imprima a classe de p max 26 ⟩;

}

This code is used in section 5.

25. #define peso(A) ((A l) ∗ (A m)) ⟨ Verifique o peso de p e atualize o máximo caso necessário 25 ⟩ ≡

{ register long w = peso(p);

if (w > pp) { p max = p; pp = w; } }

This code is used in section 24.

26. ⟨ Imprima a classe de p max 26 ⟩ ≡

if (p max ) { register link q = p max h;

    printf (  ␣      ␣  ␣      ␣     ␣   ␣         ␣  ␣          ␣   ␣      ␣  ,

p max m, p max l, peso(p max )); while (q) {

printf ( ␣␣ , q w);

q = q next ; } printf ( ␣ ␣ ␣ ␣ ␣ ␣ , N classes );

}

This code is used in section 24.

27. Precisamos determinar os maiores pesos que obtivemos. Para tanto, usamos um counting sort, que nada mais é que a classificação de todas as classes de equivalência em “baldes” indexados pelos respectivos pesos. Supomos que o número máximo de classes que teremos é .

#define  500

⟨ Imprima as classes cujos pesos são os n pesos maiores pesos 27 ⟩ ≡

{ node ∗bucket [ + 1]; register node ∗∗p; printf ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ); fflush(stdout ); /∗ progress report ∗/ for (p = bucket ; p ≤ bucket + ; p^{++}) ∗p = Λ; ⟨ Percorra o treap e monte bucket 28 ⟩; ⟨ Imprima as classes nos maiores n pesos baldes não-vazios 30 ⟩;

}

This code is used in section 5.

28. ⟨ Percorra o treap e monte bucket 28 ⟩ ≡

{ if (root ≠ Λ) { register node ∗p, ∗q; p = root ; root = Λ; while (1) {

while (p left ≠ Λ) { q = p left ; p left = root ; /∗ usamos left para implementarmos a pilha ∗/ root = p; p = q;

} visit2 : ⟨ Coloque a classe de p no balde correspondente 29 ⟩;

if (p right ≡ Λ) { if (root ≡ Λ) break; /∗ a pilha está vazia; terminamos ∗/ p = root ; root = root left ; /∗ desempilha! ∗/ goto visit2 ;

}

else p = p right ; }

} }

This code is used in section 27.

29. Manteremos os objetos em cada balde em listas ligadas. Usamos o campo left para a lista ligada. ⟨ Coloque a classe de p no balde correspondente 29 ⟩ ≡

{ register long w = peso(p);

if (w > ) { fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣ , ∗argv ); return −7;

} p left = bucket [w]; bucket [w] = p;

}

This code is used in section 28.

30. ⟨ Imprima as classes nos maiores n pesos baldes não-vazios 30 ⟩ ≡

{ register long i; register node ∗∗p = bucket + ; for (i = 0; i < n pesos ; i^{++}) { while (¬∗p ∧ ^{−}p > bucket ) ; if (p > bucket ) ⟨ Imprima as classes em ∗p e avance p 31 ⟩ else break;

} }

This code is used in section 27.

31. ⟨ Imprima as classes em ∗p e avance p 31 ⟩ ≡

{ register node ∗pp = ∗p;

while (pp) { register link q = pp h; printf ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ , i + 1, pp m, pp l,

peso(pp)); while (q) {

printf ( ␣␣ , q w); q = q next ;

}

pp = pp left ; } p^{−};

}

This code is used in section 30.

32. Terminamos este programa com o seguinte comentário. Eu havia planejado escrever também um programa baseado na interface ST.h de Sedgewick [Algorithms in C, Third Edition, Parts 1–4]. Este é a interface para uma tabela de símbolos abstrata. Desta forma, poderíamos facilmente experimentar as várias implementações de tabelas de símbolos dadas naquele livro. Seria bastante interessante fazer um estudo empírico das várias possiblidades. Infelizmente, preciso voltar a outras tarefas e tal programa fica para outra ocasião.

Lembre que observamos acima que este programa ainda pode ser melhorado em termos de eficiência: poderíamos tirar proveito do fato de que, em geral, as buscas que fazemos em nosso treap é sem sucesso e que portanto queremos inserir elementos muito frequentemente.

12  ÍNDICE  ANAGRAMAS §33

33. Índice. Aqui está uma lista dos identificadores usados por anagramas; as seções onde eles aparecem são dadas (as entradas sublinhadas indicam os pontos de definição).

anagrama: \underline{17}, 18, 19, 23. Aragon, Cecilia Rodriguez: 9. argc: \underline{5}, 6. argv : \underline{5}, 6, 13, 23, 29. b: \underline{22}. bad cell : 15, \underline{16}, 20. bad node: 13, \underline{16}. bad string : 14, \underline{16}, 21. block size: \underline{14}, \underline{21}. bucket : \underline{27}, 29, 30. buffer : 10, 12, 13, 14, \underline{16}, 18, 19, 21, 22, 23. byte: \underline{7}, 8, 9, 14, 16, 18, 21, 22, 23. c: \underline{8}. calloc: 13, 15, 20. cell: \underline{7}, 15, 16, 20. : \underline{13}, 15, 20. : \underline{13}, 14, 21. current rank : 10, \underline{11}. done: \underline{18}, 23. : 23. ferror : 23. fflush: 27. fprintf : 6, 13, 23, 29. getchar : 23. h: \underline{9}. i: \underline{30}. keyword : \underline{9}, 10, 12, 14, 19. l: \underline{9}, \underline{16}. left : \underline{9}, 10, 12, 19, 24, 28, 29, 31. link: \underline{7}, 9, 15, 20, 26, 31. list node: \underline{7}. loco encontrado: \underline{17}, 19, 20. m: \underline{9}. main: \underline{5}. malloc: 14, 18, 21. max length: \underline{8}, 18, 23. : \underline{4}, 8. : \underline{27}, 29, 30. N classes : \underline{8}, 10, 26. n pesos : 5, 6, \underline{8}, 30. next : \underline{7}, 15, 20, 26, 31. next cell : 15, \underline{16}, 20. next node: 13, \underline{16}. next string : 14, \underline{16}, 21. node: \underline{9}, 10, 13, 16, 17, 19, 24, 27, 28, 30, 31. node struct: \underline{9}. : \underline{13}. out of mem: \underline{13}, 14, 15, 18, 20, 21. p: \underline{10}, \underline{15}, \underline{19}, \underline{20}, \underline{22}, \underline{24}, \underline{27}, \underline{28}, \underline{30}. p max : \underline{24}, 25, 26. palavra corrente: 15, \underline{16}, 20, 21. peso: \underline{25}, 26, 29, 31. : \underline{9}, 10. pp: \underline{24}, 25, \underline{31}. printf : 26, 27, 31. q: \underline{10}, \underline{22}, \underline{24}, \underline{26}, \underline{28}, \underline{31}. qq : \underline{10}, 12. r: \underline{10}. rank : \underline{9}, 10. right : \underline{9}, 10, 12, 19, 24, 28. root : 10, \underline{16}, 19, 24, 28. Seidel, Raimund: 9. sscanf : 6. stderr : 5, 6, 13, 23, 29. stdin: 2, 19, 23. stdout : 2, 5, 27. strcmp: 19. u: \underline{8}. v: \underline{8}. visit : \underline{24}. visit2 : \underline{28}. w: \underline{7}, \underline{25}, \underline{29}.

ANAGRAMAS NAMES OF THE SECTIONS 13

⟨ Canonize buffer 22 ⟩ Used in section 21.

⟨ Coloque a classe de p no balde correspondente 29 ⟩ Used in section 28. ⟨ Copie buffer na memória alocada para strings e faça r keyword apontar para esta cópia 14 ⟩ Used in

section 13.

⟨ Encontre uma classe de equivalência de peso máximo e imprima 24 ⟩ Used in section 5. ⟨ Faça uma cópia de buffer na memória alocada para strings e canonize buffer “in loco” 21 ⟩ Used in

section 18.

⟨ Faça r apontar para um novo nó e ponha buffer neste nó 13 ⟩ Used in section 10. ⟨ Imprima a classe de p max 26 ⟩ Used in section 24. ⟨ Imprima as classes cujos pesos são os n pesos maiores pesos 27 ⟩ Used in section 5. ⟨ Imprima as classes em ∗p e avance p 31 ⟩ Used in section 30. ⟨ Imprima as classes nos maiores n pesos baldes não-vazios 30 ⟩ Used in section 27. ⟨ Insira o nó correspondente a buffer no treap 10 ⟩ Used in section 18.

⟨ Insira palavra corrente na lista de r 15 ⟩ Used in section 13. ⟨ Insira palavra corrente na lista do loco encontrado 20 ⟩ Used in section 18.

⟨ Interprete a linha de comando 6 ⟩ Used in section 5. ⟨ Leia em buffer a próxima palavra em stdin; goto done caso o arquivo terminou 23 ⟩ Used in section 18. ⟨ Percorra o treap e monte bucket 28 ⟩ Used in section 27. ⟨ Processe a lista de palavras 18 ⟩ Used in section 5.

⟨ Procure buffer no treap 19 ⟩ Used in section 18.

⟨ Quebre a subárvore p e pendure as duas árvores resultantes em r 12 ⟩ Used in section 10.

⟨ Typedefs 7, 9 ⟩ Used in section 5. ⟨ Variáveis locais 8, 11, 16, 17 ⟩ Used in section 5.

⟨ Verifique o peso de p e atualize o máximo caso necessário 25 ⟩ Used in section 24.

ANAGRAMAS

Section Page

Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Treaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 12