Search engine problem solution

#include<iostream>
#include<string>

using namespace std;

const int alphabet=26;

struct trie
{
    int weight;
    struct trie *child[alphabet];
    bool endword;
};

struct trie *newnode()
{
    struct trie *node=new trie;
    node->endword=false;
    node->weight=-1;
    for(int i=0;i<alphabet;i++)
    {
        node->child[i]=NULL;

    }
    return node;

}

void insert(struct trie *root,string key,int x)
{
    struct trie *temp=root;         //store the root in a temp node
    for(int i=0;i<key.length();i++)
    {
        int index=key[i]-'a';              // check if the character does not exceed english alphabet
        if(!temp->child[index]) {          //if the character does not exist , then create a new
                                         //and change the temp pointer
        temp->child[index]=newnode();
        }
       temp=temp->child[index];
       if(temp->weight<x)              // if the weight of the node is lesser, then update the weight.
          temp->weight=x;
    }
    temp->endword=true;                    //this marks the end of a word in string

}

void search(struct trie *root,string key)
{    if(root==NULL)
        return;

    struct trie *temp=root;

    for(int i=0;i<key.length();i++)
    {
        int index=key[i]-'a';               //check overflow for characters
        if(!temp->child[index])              //if index is false , the return false
            return;
        temp=temp->child[index];             //go the next child
    }
    cout<<temp->weight<<endl;
}

int main()
{

    int n , q;
    cin>>n;                             // enter the number of database items
    cin>>q;                             // enter the number of items to be searched
    struct trie *root = newnode();
    while(n--)
    {
        string s;                       
        int w;
        cin>>s>>w;                      ////enter the database item i.e strings and their weights.
        insert(root,s,w);
    }
    while(q--)
    {
        string s;
        cin>>s;
        search(root,s);

    }

     return 0;
}

Contact us





JDoodle for WordPress
Scroll Up