trie

#include <iostream>
#include<bits/stdc++.h>
#define hashmap unordered_map<char,node*>
using namespace std;

class node{
   public:
    char data;
    hashmap h;
    bool isTerminal;
    node(char d){
        data=d;
        isTerminal=false;
    }
};

class trie{
    node *root;
    public:
        trie(){
            root=new node('\0');
        }

        //inserting values into trie
        void insert(string word){
            node *temp=root;
            int n=word.length();
            for(int i=0; i<n; i++){
                char ch=word[i];
                if(temp->h[ch]==0){
                    node *child=new node(ch);
                    temp->h[ch]=child;
                    temp=child;
                }
                else{
                    temp=temp->h[ch];
                }
            }
            temp->isTerminal=true;
        }

        //searching for a word in trie
        bool search(string word){
            node *temp=root;
            int n=word.length();
            for(int i=0; i<n; i++){
                char ch=word[i];
                if(temp->h.count(ch))
                    temp=temp->h[ch];
                else
                    return false;
            }
            return temp->isTerminal;
        }
};

int main() {
    int t;
    cin>>t;
    while(t--){
        int n; cin>>n;
        string s[n];
        for(int i=0; i<n; i++){
            cin>>s[i];
        }

        trie t;
        for(int i=0; i<n; i++){
            t.insert(s[i]);
        }
        string word;
        cin>>word;

        if(t.search(word)) cout<<1<<endl;
        else cout<<0<<endl;
    }

}