Searching string using Trie tree (Basic code of Trie tree)

 

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

#include <bits/stdc++.h>

using namespace std;

struct node

{

    bool mark=0;

    node* child[52]= {NULL};

};

node *root=new node;

int getld(char ch)

{

    int id=ch-'A';

    if(ch>='a')id-=6;

    return id;

}

void insert(string s)

{

    node *crnt=root;

    for(int i=0;i<s.size();i++)

    {

        int id=getld(s[i]);

        if(crnt->child[id]==NULL)

           crnt->child[id]=new node;

        crnt=crnt->child[id];

    }

    crnt->mark=1;

}

bool search (string &s)

{

    node *currentnode=root;

    for(int i=0;i<s.size();i++)

    {

       int id=getld(s[i]);

        if(currentnode->child[id]==NULL)

            return false;

        currentnode=currentnode->child[id];

    }

    return currentnode->mark;

}

int main()

{

    int n;

    string s,s1;

    cout<<" number of string given : "<<endl;

    cin>>n;

    for(int i=0; i<n; i++)

    {

        cin>>s;

        insert(s);

    }

    cout<<" Searching string  : "<<endl;

    cin>>s1;

    if(search(s1))

    {

        cout<<s1<<" found\n";

    }

    else

    {

        cout<<s1<<" not found\n";

    }

    return 0;

}