Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

[algogeeks] Re: TRIE problem pavan Wed Feb 15 22:00:43 2012

i am getting WA by implementing TRIE .can anyone help me with the test
cases for which the following code is failing.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#define MAX 26
#define LEN 1000
using namespace std;


struct node
{
        char c;
        int isterminal;
        int no_children;
        struct node* children[MAX];
};
struct node* createnode(char ch)
{
        struct node* nl=(struct node*)malloc(sizeof(struct node));
        if(nl==NULL)
        printf("memory allocation error");
        else
        {
                nl->c=ch;
                nl->no_children=0;
                nl->isterminal=-1;
        }
        return nl;
}
struct node* insert(char* str,int i,int len,struct node* root)
{
        char ch=str[i];
        if(i==len)
        {
                root->isterminal=1;
                return root;
        }
        if(root->children[ch-'a']==NULL || root->children[ch-'a']-
>isterminal==-1)
        {
                struct node* nl=createnode(ch);
                root->children[ch-'a']=nl;
                root->children[ch-'a']->isterminal=0;
                root->no_children++;
        }
        root->children[ch-'a']=insert(str,i+1,len,root->children[ch-'a']);
        return root;
}
int countchildren(struct node* root,char* buffer,int len)
{
        int index=0;
        static int count=0;
        if(root->isterminal==1)
        {
                printf("%s\n",buffer);
                count++;
        }
        for(int i=0;i<MAX;i++)
        {
                        if(root->children[i]!=NULL)
                        {
                                buffer[len]=root->children[i]->c;
                                buffer[len+1]='\0';
                                countchildren(root->children[i],buffer,len+1);
                        }
        }
        return count;
}
int solve(char* str,int i,int len,struct node* root)
{
        int c;
        char ch=str[i];
        char buffer[LEN];
        if(i<len)
        {
                if(root==NULL || root->children[ch-'a']==NULL)
                return 0;
                else
                {
                        return solve(str,i+1,len,root->children[ch-'a']);
                }
        }
        else
        {
                strcpy(buffer,str);
                c=countchildren(root,buffer,strlen(str));
                //printf("count %d\n",c);
                return 1;
        }
}
int main()
{
        struct node* trie=createnode('$');
        char str[1000];
        int t,k;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%s",str);
                trie=insert(str,0,strlen(str),trie);
        }
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
                scanf("%s",str);
                printf("Case #%d:\n",i);
                if(!solve(str,0,strlen(str),trie))
                        printf("No match.\n");
        }
        return 0;
}

On Feb 15, 11:56 am, shady <[EMAIL PROTECTED]> wrote:
> will TRIE be the best solution for this problem ?
>
> Link<http://www.spoj.pl/problems/DICT/>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.