Trie



#include <bits/stdc++.h>

using namespace std;

char ara[100000];

struct node
{
    bool endmark;
    node *data[26];
    node()
    {
        endmark=0;
        for(int i=0;i<26;i++)
            data[i]= NULL;
    }
}*root;

void insert(char *str,int len)
{
    node *curr = root;
    for(int i=0;i<len;i++)
    {
        int indx=str[i]-'a';
        if(curr->data[indx]==NULL)
            curr->data[indx]=new node;
        curr = curr->data[indx];
    }
    curr->endmark=1;
}

bool search(char *str,int len)
{
    node *curr=root;
    for(int i=0;i<len;i++)
    {
        int indx=str[i]-'a';
        if(curr->data[indx]==NULL)
            return false;
        curr=curr->data[indx];
    }
    return curr->endmark;
}

void del(node *cur)
{
    for(int i=0;i<26;i++)
        if(cur->data[i])
            del(cur->data[i]);
    delete cur;
}

int main()
{
    int n,m;
    cin>>n>>m;
    root = new node;
    getchar();
    while(n--)
    {
        scanf("%s",ara);
        getchar();
        insert(ara,strlen(ara));
    }

    while(m--)
    {
        scanf("%s",ara);
        getchar();
        if(search(ara,strlen(ara)))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    del(root);
    return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s