//Trie Implementation
//Complexity:   O(Length of String) look up/insertion time
//Author:       Rajiv Mathews
//NOTE          Use g++ -O2 for faster map
class trie {
private:
        map<char, struct trie *> next;
        bool is_word;
public:
        //Add given word (string) to the trie
        void add_word(string s)
        {
                trie *curr_node = this;
                for(int i = 0 ; s[i] != '\0' ; ++i) {
                        if(curr_node->next[s[i]] == NULL) curr_node->next[s[i]] = new trie();
                        curr_node = curr_node->next[s[i]];
                }
                curr_node->is_word = true;
        }
        //Check if given word (string) is present in the trie
        bool is_present(string s)
        {
                trie *curr_node = this;
                for(int i = 0 ; s[i] != 0 ; ++i) {
                        if(curr_node->next[s[i]] == NULL) return false;
                        curr_node = curr_node->next[s[i]];
                }
                return curr_node->is_word;
        }
};