#include <stdio.h>
#include <stdlib.h>

#define WORD_LEN 255
#define ALPHABET_SIZE 26

struct trie_node {
      struct trie_node *next[ALPHABET_SIZE];
      int count;
   };
typedef struct trie_node TRIE_NODE;

struct dict_desc {
      char name[WORD_LEN];
      int size;
   };
typedef struct dict_desc DICT_DESC;

void trie_add(TRIE_NODE *root, const char *word)
{
   TRIE_NODE *cur_root = root;

   while (*word)
   {
      if (!cur_root->next[*word-'a'])
      {
         cur_root->next[*word-'a'] = malloc(sizeof(TRIE_NODE));
         for (int i=0; i<ALPHABET_SIZE; i++)
            cur_root->next[*word-'a']->next[i] = NULL;
         cur_root->next[*word-'a']->count = 0;
      }

      cur_root = cur_root->next[*word-'a'];
      ++word;
   }
   //Není potřeba si pamatovat konce slov, v zavěrečném počítání se hodnoty
   //v nekoncových uzlech zanedbají
}

void trie_increase_word_count(TRIE_NODE *root, const char *word)
{
   TRIE_NODE *cur_root = root;    //poslední fáze, máme jistotu že slovo najdeme

   while (*word && cur_root)
   {
      cur_root = cur_root->next[*word-'a'];
      ++word;
   }
   if (cur_root)
      cur_root->count++;
}

int trie_find(TRIE_NODE *root, const char *word)
//nalezne slovo v trii a vrátí, kolikrát se vyskytlo
{
   TRIE_NODE *cur_root = root;    //poslední fáze, máme jistotu že slovo najdeme

   while (*word)
   {
      cur_root = cur_root->next[*word-'a'];
      ++word;
   }
   return cur_root->count;
}

void trie_free(TRIE_NODE *root)  //uvolnění struktur
{
   if (!root)
      return;
   for(int i=0; i<ALPHABET_SIZE; i++)
      trie_free(root->next[i]);
   free(root);
}

TRIE_NODE *trie_root;
int N;

int main(void)
{
   trie_root = malloc(sizeof(TRIE_NODE));
   for (int i=0; i<ALPHABET_SIZE; ++i)
      trie_root->next[i] = NULL;
   trie_root->count = 0;

   //inicializace trie
   FILE *fdict = fopen("slovniky.in", "r");
   int dict_count;
   fscanf(fdict, "%d", &dict_count);
   for (int dict=0; dict<dict_count; dict++)
   {
      int dict_size;
      char word[WORD_LEN+1];
      fscanf(fdict, "%s %d", word, &dict_size);
      for(int cur_word=0; cur_word<dict_size; cur_word++)
      {
         fscanf(fdict, "%s", word);
         trie_add(trie_root, word);
      }
   }
   fclose(fdict);

   //zjištění počtů slov v textu
   FILE *ftext = fopen("text.in", "r");
   while( !feof(ftext))
   {
      char word[WORD_LEN+1];
      fscanf(ftext, " %s ", word);
      trie_increase_word_count(trie_root, word);
   }
   fclose(ftext);

   //zjištění počtů slov ve slovnících
   fdict = fopen("slovniky.in", "r");
   fscanf(fdict, "%d", &dict_count);
   DICT_DESC *dict_desc = malloc(sizeof(DICT_DESC) * dict_count);

   for (int dict=0; dict<dict_count; dict++)
   {
      int dict_size;
      fscanf(fdict, "%s %d", dict_desc[dict].name, &dict_size);
      dict_desc[dict].size = 0;

      for(int cur_word=0; cur_word<dict_size; cur_word++)
      {
         char word[WORD_LEN+1];
         fscanf(fdict, "%s", word);
         dict_desc[dict].size+= trie_find(trie_root, word);
      }
   }
   fclose(fdict);

   //nalezení slovníků s největším počtem slov
   int max = 0;
   for (int dict=0; dict<dict_count; dict++)
      if (dict_desc[dict].size>max)
         max = dict_desc[dict].size;

   //vypsání slovníků
   FILE *fout = fopen("jazyk.out", "w");
   for (int dict=0; dict<dict_count; dict++)
      if (dict_desc[dict].size==max)
         fprintf(fout, "%s\n", dict_desc[dict].name);
   fclose(fout);

   //uvolnění trie
   trie_free(trie_root);
   return 0;
}