#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct trie
{
char value;
int end;
struct trie *child;
struct trie *sibling;
} * Trie;
Trie initTrie(char value, int end)
{
Trie root = malloc(sizeof(struct trie));
root->value = value;
root->end = end;
root->child = NULL;
root->sibling = NULL;
return root;
}
Trie insertChild(Trie trie, char value, int end)
{
if (trie == NULL)
{
return initTrie(value, end);
}
if (trie->child == NULL)
{
trie->child = initTrie(value, end);
return trie;
}
Trie tmp = trie->child;
while (tmp->sibling != NULL)
{
tmp = tmp->sibling;
}
tmp->sibling = initTrie(value, end);
return trie;
}
Trie getChild(Trie trie, char value)
{
if (trie == NULL)
{
return NULL;
}
Trie tmp = trie->child;
while (tmp != NULL)
{
if (tmp->value == value)
{
return tmp;
}
tmp = tmp->sibling;
}
return NULL;
}
Trie insertWord(Trie trie, char *word, int index)
{
if (index == strlen(word))
{
trie->end++;
return trie;
}
Trie child;
child = getChild(trie, word[index]);
if (child == NULL)
{
trie = insertChild(trie, word[index], 0);
child = getChild(trie, word[index]);
}
child = insertWord(child, word, index + 1);
return trie;
}
int containsWord(Trie trie, char *word, int index)
{
if (index == strlen(word) && trie->end >= 1)
{
return trie->end;
}
Trie p = trie->child;
while (p)
{
if (p->value == word[index])
return containsWord(p, word, index + 1);
p = p->sibling;
}
return 0;
}
Trie deleteChild(Trie trie, char value)
{
if (!trie)
return NULL;
Trie p = trie->child;
if (trie->child->value == value)
{
Trie todel = trie->child;
trie->child = trie->child->sibling;
free(todel);
return NULL;
}
while (p->sibling)
{
if (p->sibling->value == value)
{
Trie todel = p->sibling;
p->sibling = p->sibling->sibling;
free(todel);
return NULL;
}
p = p->sibling;
}
return trie;
}
Trie deleteWord(Trie trie, char *word, int index)
{
Trie p = trie->child;
while (p)
{
if (p->value == word[index])
{
if (index == strlen(word) - 1)
p->end--;
else
deleteWord(p, word, index + 1);
}
if (p->child == NULL && !p->end)
{
deleteChild(trie, p->value);
return trie;
}
p = p->sibling;
}
return trie;
}
int longest_prefix(Trie trie, char *word, int index)
{
Trie p = trie->child;
while (p)
{
if (p->value == word[index])
return longest_prefix(p, word, index + 1);
p = p->sibling;
}
return index;
}
Trie freeTrie(Trie trie)
{
Trie p = trie->child;
while (p)
{
freeTrie(p);
Trie todel = p;
p = p->sibling;
free(todel);
}
return trie;
}
int main()
{
FILE *in = fopen("trie.in", "r");
FILE *out = fopen("trie.out", "w");
Trie trie = NULL;
trie = initTrie(' ', 0);
int op;
char cuv[30];
while (fscanf(in, "%d %s", &op, cuv) == 2)
{
if (op == 0)
trie = insertWord(trie, cuv, 0);
else if (op == 1)
trie = deleteWord(trie, cuv, 0);
else if (op == 2)
fprintf(out, "%d\n", containsWord(trie, cuv, 0));
else
fprintf(out, "%d\n", longest_prefix(trie, cuv, 0));
}
trie = freeTrie(trie);
fclose(in);
fclose(out);
return 0;
}