I think you should use TST data structure for this problem.
You can find some implementation HERE <http://bit.ly/ADPNn5>
On Thu, Feb 16, 2012 at 11:32 AM, pavan <pavankri...@gmail.com> wrote:
> 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 <sinv...@gmail.com> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
