#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
struct trie_node{
int value;
trie_node *child[27];
};
struct trie{
struct trie_node *root;
int count;
};
trie_node * getnode()
{
// trie_node *ptrie=new trie_node;
trie_node *ptrie = (trie_node *)malloc(sizeof(struct trie_node));
if(ptrie)
{
ptrie->value=0;
for(int i=0;i<27;i++)
ptrie->child[i]=NULL;
}
return ptrie;
}
void init(struct trie **t)
{
(*t)->root=getnode();
(*t)->count=0;
}
void insert(struct trie **t, char key[])
{
(*t)->count++;
trie_node *p ;
p=(*t)->root;
int len=strlen(key);
int i;
for(i=0;i<27;i++)
{
// if(p->child[i]==NULL)
// cout<<"Y ";
// else cout<<"N ";
}
// cout<<endl;
for(i=0;i<len;i++)
{
int idx=key[i]-'a';
// cout<<" "<<key[i]<<": ";
if(!(p->child[idx]))
{
// cout<<idx;
p->child[idx]=getnode();
}
p=p->child[idx];
}
// cout<<endl;
p->value=(*t)->count;
}
bool search(struct trie* t, char key[])
{
int len=strlen(key);
int i;
struct trie_node *p= (t)->root;
for(i=0;i<len;i++)
{
int check= (int)key[i]-(int)'a';
if(!(p->child[check]))
return 1;
p=p->child[check];
}
return 0;
}
int main()
{
char key[][6]={"hi", "hello", "you", "ekta", "me"};
trie *t;
init(&t);
int i;
for(i=0;i<5;i++)
insert(&t,key[i]);
char output[][4]={"YES", "NO"};
cout<<output[search(t, "me")]<<endl;
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZy5oPgojaW5jbHVkZTxzdGRsaWIuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCB0cmllX25vZGV7CmludCB2YWx1ZTsKdHJpZV9ub2RlICpjaGlsZFsyN107Cn07CgpzdHJ1Y3QgdHJpZXsKIHN0cnVjdCB0cmllX25vZGUgKnJvb3Q7CiBpbnQgY291bnQ7Cn07Cgp0cmllX25vZGUgKiBnZXRub2RlKCkKewogICAvLyB0cmllX25vZGUgKnB0cmllPW5ldyB0cmllX25vZGU7CiAgIHRyaWVfbm9kZSAqcHRyaWUgPSAodHJpZV9ub2RlICopbWFsbG9jKHNpemVvZihzdHJ1Y3QgdHJpZV9ub2RlKSk7CiAgIGlmKHB0cmllKQogICB7CiAgICBwdHJpZS0+dmFsdWU9MDsKICAgIGZvcihpbnQgaT0wO2k8Mjc7aSsrKQogICAgcHRyaWUtPmNoaWxkW2ldPU5VTEw7CiAgIH0KICAgIHJldHVybiBwdHJpZTsKfQoKdm9pZCBpbml0KHN0cnVjdCB0cmllICoqdCkKewogICAoKnQpLT5yb290PWdldG5vZGUoKTsKICAgKCp0KS0+Y291bnQ9MDsgCn0KCnZvaWQgaW5zZXJ0KHN0cnVjdCB0cmllICoqdCwgY2hhciBrZXlbXSkKewogICAgCiAgICAoKnQpLT5jb3VudCsrOwogICAgdHJpZV9ub2RlICpwIDsKICAgIHA9KCp0KS0+cm9vdDsKICAgIAogICAgaW50IGxlbj1zdHJsZW4oa2V5KTsKICAgIGludCBpOwogICAgZm9yKGk9MDtpPDI3O2krKykKICAgICB7CiAgICAgLy8JaWYocC0+Y2hpbGRbaV09PU5VTEwpCiAgICAgLy8JY291dDw8IlkgIjsKICAgICAvLwllbHNlIGNvdXQ8PCJOICI7CiAgICAgfQogIC8vICAgY291dDw8ZW5kbDsKICAgIGZvcihpPTA7aTxsZW47aSsrKQogICAgewogICAgICAgIGludCBpZHg9a2V5W2ldLSdhJzsKICAgICAgLy8gIGNvdXQ8PCIgIjw8a2V5W2ldPDwiOiAiOwogICAgICAgIGlmKCEocC0+Y2hpbGRbaWR4XSkpCiAgICAgICAgewogICAgICAgIC8vCWNvdXQ8PGlkeDsKICAgICAgICAgICAgcC0+Y2hpbGRbaWR4XT1nZXRub2RlKCk7CiAgICAgICAgfQogICAgICAgIHA9cC0+Y2hpbGRbaWR4XTsKICAgIH0KICAgLy8gY291dDw8ZW5kbDsKICAgIHAtPnZhbHVlPSgqdCktPmNvdW50Owp9Cgpib29sIHNlYXJjaChzdHJ1Y3QgdHJpZSogdCwgY2hhciBrZXlbXSkKewogICAgaW50IGxlbj1zdHJsZW4oa2V5KTsKICAgIGludCBpOwogICAgc3RydWN0IHRyaWVfbm9kZSAqcD0gKHQpLT5yb290OwogICAgZm9yKGk9MDtpPGxlbjtpKyspCiAgICB7CiAgICAgICAgaW50IGNoZWNrPSAoaW50KWtleVtpXS0oaW50KSdhJzsKICAgICAgICBpZighKHAtPmNoaWxkW2NoZWNrXSkpCiAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgCiAgICAgICAgcD1wLT5jaGlsZFtjaGVja107CiAgICB9CiAgICAKICAgIHJldHVybiAwOwp9CgppbnQgbWFpbigpCnsKICAgIGNoYXIga2V5W11bNl09eyJoaSIsICJoZWxsbyIsICJ5b3UiLCAiZWt0YSIsICJtZSJ9OwogICAgdHJpZSAqdDsKICAgIGluaXQoJnQpOwogICAgaW50IGk7CiAgICBmb3IoaT0wO2k8NTtpKyspCiAgICAgaW5zZXJ0KCZ0LGtleVtpXSk7CiAgICAgCiAgICAgY2hhciBvdXRwdXRbXVs0XT17IllFUyIsICJOTyJ9OwogICAgIAogICAgIGNvdXQ8PG91dHB1dFtzZWFyY2godCwgIm1lIildPDxlbmRsOwogICAgcmV0dXJuIDA7Cn0=