#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct Trie
{
int count;
int appearances;
struct Trie* letters[26];
} TRIE, *PTRIE;
void
addWordToTrie(PTRIE trie,
char* word)
{
++(trie -> count);
if ('\n' == *word)
{
++(trie -> appearances);
return;
}
if (NULL == (trie -> letters)[*word - 'a'])
{
(trie -> letters)[*word - 'a'] = (PTRIE)malloc(sizeof(TRIE));
for (int i = 0; i < 26; ++i)
{
((trie -> letters)[*word - 'a'] -> letters)[i] = NULL;
}
(trie -> letters)[*word - 'a'] -> count = 0;
(trie -> letters)[*word - 'a'] -> appearances = 0;
}
addWordToTrie( (trie -> letters)[*word - 'a'],
(word + 1) );
}
/* ----------------------------------------------------------------------- */
_Bool
wordExistsInTrie(PTRIE trie,
char* word)
{
if (NULL == trie)
{
return false;
}
if (NULL == word)
{
return false;
}
if ('\n' == *word)
{
return true;
}
if (NULL != (trie -> letters)[*word - 'a'])
{
return wordExistsInTrie((trie -> letters)[*word - 'a'],
(word + 1));
}
else
{
return false;
}
}
/* ----------------------------------------------------------------------- */
void
removeWordFromTrie(PTRIE trie,
char* word)
{
if (NULL == trie)
{
return;
}
if (NULL == word)
{
return;
}
--(trie -> count);
if ('\n' == *word)
{
--(trie -> appearances);
return;
}
removeWordFromTrie( (trie -> letters)[*word - 'a'],
(word + 1) );
if (0 == (trie -> letters)[*word - 'a'] -> count)
{
free((trie -> letters)[*word - 'a']);
(trie -> letters)[*word - 'a'] = NULL;
}
}
/* ----------------------------------------------------------------------- */
int
getNumberOccurrences(PTRIE trie,
char* word)
{
if (NULL == trie)
{
return 0;
}
if ('\n' == *word)
{
return trie -> appearances;
}
return getNumberOccurrences( (trie -> letters)[*word - 'a'],
(word + 1) );
}
/* ----------------------------------------------------------------------- */
int
getLengthOfLongestCommonPrefix(PTRIE trie,
char* word)
{
if (NULL == trie)
{
return 0;
}
if ( (NULL == word) ||
('\n' == *word) )
{
return 0;
}
if (NULL != (trie -> letters)[*word - 'a'])
{
return (1 + getLengthOfLongestCommonPrefix( (trie -> letters)[*word - 'a'],
(word + 1) ));
}
else
{
return 0;
}
}
/* ----------------------------------------------------------------------- */
int main()
{
char w[50];
TRIE* trie;
trie = (PTRIE)malloc(sizeof(TRIE));
for (int i = 0; i < 26; ++i)
{
(trie -> letters)[i] = NULL;
}
freopen("trie.in", "r", stdin);
freopen("trie.out", "w", stdout);
fgets(w, 50, stdin);
while (!feof(stdin) )
{
if ('0' == *w)
{
addWordToTrie(trie, w + 2);
}
else if ('1' == *w)
{
removeWordFromTrie(trie, w + 2);
}
else if ('2' == *w)
{
printf("%d\n", getNumberOccurrences(trie, w + 2));
}
else
{
printf("%d\n", getLengthOfLongestCommonPrefix(trie, w + 2));
}
fgets(w, 50, stdin);
}
return 0;
}