fork download 
  1. #include<conio.h>
  2. #include<iostream.h>
  3. #include<malloc.h>
  4. #include<string.h>
  5. #define ALPHA 26
  6. #define true 1
  7. #define false 0
  8. #define n 6 //num of rows in input array
  9.  
  10. struct node 
  11. {
  12. int is_end;
  13. int prefix_count;
  14. char ch;
  15. struct node *children[ALPHA];
  16. };
  17. int search(struct node *trie);
  18. struct node *trie = NULL;
  19. int display(struct node *trie);
  20. struct node *newnode();
  21. int insert(char *s);
  22. int findall(struct node*trie,char *s);
  23. struct node *newnode()
  24. {
  25. 	struct node *temp = (struct node*)malloc(sizeof(struct node));
  26. 	temp->is_end = 0;
  27. 	temp->prefix_count = 0;
  28. 	temp->ch = '0';
  29. 	for(int i=0;i<ALPHA;i++)
  30. 	temp->children[i] = NULL;
  31. 	return temp;
  32. }
  33. int insert(char *s)
  34. {
  35. 	struct node *head = trie; 
  36. 	if(s==NULL)
  37. 	return 0;
  38. 	head->prefix_count++;
  39. 	int len = strlen(s) , i;
  40. 	for(i=0;i<len;i++)
  41. 	{
  42. 		int letter = (int)s[i] - (int) 'a';
  43. 		if(head->children[letter]==NULL)
  44. 		head->children[letter] = newnode();//create the node only if above condition is true else prefix_count has to increase in any case
  45.  
  46. 			head->children[letter]->ch = s[i];
  47. 			head->children[letter]->prefix_count ++;
  48. 			head= head->children[letter];
  49.  
  50.  
  51.  
  52.  
  53. 	}head->is_end = true; //end is reached
  54.  
  55. }//end of function
  56.  
  57.  
  58. int findall(struct node*trie,char *s)
  59. {
  60. 	int i = 0;
  61. 	struct node *current = trie;
  62. 	for(i=0;i<ALPHA;i++)
  63. 	{
  64. 		if(current->children[i]!=NULL && current->children[i]->ch==s[i])
  65. 		current = current->children[i];
  66. 	}
  67. 		search(current);
  68. 	//I have got the last string matched in cuurent;
  69. 	/*int k = current->prefix_count;
  70. 	cout<<"\n "<<s <<" is a prefix in "<<k<<" number of cases ";
  71. 	int save = 0;
  72. 	int flag = 0;
  73. 	int count = 1;
  74. 	struct node *ptr;
  75. 	save = -1;
  76. 	while(k>0)
  77. 	{	ptr = current;
  78. 		flag = 0; 
  79.  
  80.  
  81. 		for(i=save + 1;i<ALPHA;i++) //cz if 'd' at save position has been displayed next one should be  e
  82. 		{
  83. 			if(ptr->is_end==0 && ptr->children[i]!=NULL )
  84. 			{
  85. 				if(flag==0)//signal for storing save
  86. 				{	cout<<"\n ";
  87. 					save = i;//to save this value of i such that nexttime search begins from i+1 position
  88. 					flag = 1;
  89. 				}
  90. 				cout<<" "<<ptr->children[i]->ch;
  91. 				ptr = ptr->children[i];
  92.  
  93.  
  94. 			}
  95. 			if(ptr->is_end==1) //successfully displayed one string
  96. 			{k--;break;}
  97. 		}
  98.  
  99. 	}
  100.  
  101. */
  102. }
  103. int search(struct node *current)
  104. {
  105.      int i;
  106.      if(current==NULL)
  107.      return 0;
  108. 	 struct node *curr = current;
  109.  cout<<" received  "<<curr->ch;
  110.      for(i=0;i<26;i++)
  111.      {
  112.                       if(curr->children[i]!=NULL && curr->is_end==0)
  113.                       {
  114.                       search(curr->children[i]);
  115.                       }
  116.                       cout<<"   "<<curr->children[i]->ch;
  117.  
  118.  
  119.      }
  120.  
  121.  
  122.  
  123.      }
  124. int main()
  125. {
  126. 	char inp[6][15]={"abcde","abcegh","abcpqr","abcxyz","xyz" ,"abcmno"};
  127. 	int i ;
  128.  
  129. 	trie = newnode();
  130. 	for(i=0;i<n;i++)
  131. 	insert(inp[i]);
  132. 	cout<<"\n";
  133. 	char pre[] = "abc";
  134. 	findall(trie,pre);
  135. getch();
  136. return 0;
  137. }
  138.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:1:18: error: conio.h: No such file or directory
prog.cpp:2:21: error: iostream.h: No such file or directory
prog.cpp: In function ‘int search(node*)’:
prog.cpp:109: error: ‘cout’ was not declared in this scope
prog.cpp: In function ‘int main()’:
prog.cpp:132: error: ‘cout’ was not declared in this scope
prog.cpp:135: error: ‘getch’ was not declared in this scope
stdout 
Standard output is empty
https://ideone.com/UhTTx
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!