trie.cpp

/* Trie */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

struct trie{
    map<char, trie*> children;
};


bool noPrefixInsert(trie *t, string &word)
{
    trie* curr = t;
    for(int i=0; i<word.length(); i++){
        if(curr->children['$']) return false;

        if(!curr->children[word[i]]) curr->children[word[i]] = new trie;

        curr = curr->children[word[i]];
    }

    if(curr->children.size() > 0) return false;

    curr->children['$'] = new trie;
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);

    trie* dictionary = new trie;

    for(int i=0; i<n; i++){
        string word;
        cin >> word;

        if(!noPrefixInsert(dictionary, word)){
            cout << "BAD SET" << endl << word;
            return 0;
        }
    }
    cout << "GOOD SET";
}