trie.cpp

#include <bits/stdc++.h>
using namespace std;
const int Max_char=26;

struct trie{
    trie *child[Max_char];
    bool isendofword;
};
trie *getnode(){
    trie *p=new trie;
    p->isendofword=false;
    for(int i=0;i<Max_char;i++){
        p->child[i]=NULL;
    }
    return p;
}
void insert(trie *root,string s){
    trie *p=root;
    for(int i=0;i<s.size();i++){
        int index=s[i]-'a';
        if(p->child[index]==NULL){
            p->child[index]=getnode();
        }
        p=p->child[index];
    }
    p->isendofword=true;
}
bool search(trie *root,string s){
    trie *p=root;
    for(int i=0;i<s.size();i++){
        int index=s[i]-'a';
        if(p->child[index]==NULL){
            return false;
        }
        p=p->child[index];
    }
    return (p!=NULL && p->isendofword);
}

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    string str;
	    trie *root=getnode();
	    while(n--){
	        cin>>str;
	        insert(root,str);
	    }
	    cin>>str;
	    if(search(root,str)) cout<<"1\n";
	    else cout<<"0\n";
	}
	return 0;
}