// Arup Guha
// 1/8/2020
// Solution to Jan 2020 Foundation Exam Section 1 B Question 3

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

typedef struct TrieNode {
    struct TrieNode *children[26];
    int flag; // 1 if the string is in the trie, 0 otherwise
    int numwords; // the total # of words stored in this sub-trie.
} TrieNode;

int printWords(TrieNode* root, int freq[], char* cur, int k);
TrieNode* init();
void insert(TrieNode* tree, char word[], int k);

int numWordsWithPrefix(TrieNode* root, char* prefix) {

    int i, len = strlen(prefix);
    for (i=0; i<len; i++) {
        if (root->children[prefix[i]-'a'] == NULL)
            return 0;
        root = root->children[prefix[i]-'a'];
    }
    return root->numwords;
}

TrieNode* init() {

    // Create the struct, not a word.
    TrieNode* myTree = malloc(sizeof(TrieNode));
    myTree->flag = 0;
    myTree->numwords = 0;

    // Set each pointer to NULLL.
    int i;
    for (i=0; i<26; i++)
        myTree->children[i] = NULL;

    // Return a pointer to the new root.
    return myTree;
}

void insert(TrieNode* tree, char word[], int k) {

    // This is always the case, so just do it.
    tree->numwords += 1;

    // Down to the end, insert the word.
    if (k == strlen(word)) {
        tree->flag = 1;
        return;
    }

    // See if the next place to go exists, if not, create it.
    int nextIndex = word[k] - 'a';
    if (tree->children[nextIndex] == NULL)
        tree->children[nextIndex] = init();

    insert(tree->children[nextIndex], word, k+1);
}

int main() {

    FILE* ifp = fopen("dictionary.txt","r");
    int n, i;
    fscanf(ifp, "%d", &n);
    TrieNode* root = init();
    for (i=0; i<n; i++) {
        char word[100];
        fscanf(ifp,"%s", word);
        insert(root, word, 0);
    }

    printf("# of words that start with trans = %d.\n", numWordsWithPrefix(root, "transq"));

    return 0;
}