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.  
  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. 	//I have got the last string matched in cuurent;
  68. 	int k = current->prefix_count;
  69. 	cout<<"\n "<<s <<" is a prefix in "<<k<<" number of cases ";
  70. 	int save = 0;
  71. 	int flag = 0;
  72. 	int count = 1;
  73. 	struct node *ptr;
  74. 	save = -1;
  75. 	while(k>0)
  76. 	{	ptr = current;
  77. 		flag = 0; 
  78.  
  79.  
  80. 		for(i=save + 1;i<ALPHA;i++) //cz if 'd' at save position has been displayed next one should be  e
  81. 		{
  82. 			if(ptr->is_end==0 && ptr->children[i]!=NULL )
  83. 			{
  84. 				if(flag==0)//signal for storing save
  85. 				{	cout<<"\n ";
  86. 					save = i;//to save this value of i such that nexttime search begins from i+1 position
  87. 					flag = 1;
  88. 				}
  89. 				cout<<" "<<ptr->children[i]->ch;
  90. 				ptr = ptr->children[i];
  91.  
  92.  
  93. 			}
  94. 			if(ptr->is_end==1) //successfully displayed one string
  95. 			{k--;break;}
  96. 		}
  97.  
  98. 	}
  99.  
  100.  
  101.  
  102. }
  103. int main()
  104. {
  105. 	char inp[6][15]={"abcde","abcegh","abcpqr","abcxyz","xyz" ,"abcmno"};
  106. 	int i ;
  107.  
  108. 	trie = newnode();
  109. 	for(i=0;i<n;i++)
  110. 	insert(inp[i]);
  111. 	cout<<"\n";
  112. 	char pre[] = "abc";
  113. 	findall(trie,pre);
  114. getch();
  115. return 0;
  116. }
  117.  
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 findall(node*, char*)’:
prog.cpp:69: error: ‘cout’ was not declared in this scope
prog.cpp:72: warning: unused variable ‘count’
prog.cpp: In function ‘int main()’:
prog.cpp:111: error: ‘cout’ was not declared in this scope
prog.cpp:114: error: ‘getch’ was not declared in this scope
stdout 
Standard output is empty
https://ideone.com/rBvQb
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!