// Arup Guha
// 8/21/2018
// Solution to Aug 2018 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
} TrieNode;

int max(int a, int b) {
    if (a > b) return a;
    return b;
}

TrieNode* init() {

    // Create the struct, not a word.
    TrieNode* myTree = malloc(sizeof(TrieNode));
    myTree->flag = 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) {

    // 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 maxNumPrefixWords(TrieNode* root) {

    if (root == NULL) return 0;
    int maxChild = 0;
    int i;
    for (i=0; i<26; i++)
        maxChild = max(maxChild, maxNumPrefixWords(root->children[i]));

    return maxChild + root->flag;
}

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("max is %d\n", maxNumPrefixWords(root));
    return 0;
}