SPOJ – ADAINDEX – Ada and Indexing

Arunima Mandal

Problem Link: https://www.spoj.com/problems/ADAINDEX/

Note: The idea behind the problem is pretty simple. Just keep a count variable in each node while building the Trie, so that each node keeps track of its count in how many words it has been repeated.

Solution:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[26]={};
    int cnt=0;
};

void insert(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'a';
        if(!it->child[ind]) it->child[ind]= new TrieNode();
        it=it->child[ind];
        it->cnt++;
    }
}

int search(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'a';
        if(!it->child[ind]) return 0;
        it=it->child[ind];
    }
    return it->cnt;
}

int main()
{
    int n,q;
    cin>>n>>q;
    TrieNode *root=new TrieNode();
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        insert(root, s);
    }

    for(int i=0; i<q; i++)
    {
        string s;
        cin>>s;
        cout<<search(root, s)<<endl;
    }
    return 0;
}

Leave a comment