fork(2) download 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<iostream>
  5. #include<string>
  6. #include<stdlib.h>
  7. #include<vector>
  8. #include<stack>
  9. #include<queue>
  10. #include<set>
  11. #include<map>
  12. #include<algorithm>
  13. using namespace std;
  14. #define maxv(A,B) (A>B?A:B)
  15. #define minv(A,B) (A>B?B:A)
  16. #define inf 2147483647
  17. #define pi (2*acos(0.0))
  18. #define eps 1e-9
  19. int gcd(int a,int b) {return (b==0?a:gcd(b,a%b));}
  20. int lcm(int a,int b) {return (a*(b/gcd(a,b)));}
  21. int fx[]={0,0,1,-1};
  22. int fy[]={-1,1,0,0};
  23. char e;
  24. struct node
  25. {
  26. 	int endmark;
  27. 	node *next[50+1];
  28. 	node()
  29. 	{
  30. 		endmark=0;
  31. 		for(int i=0;i<51;i++) next[i]=NULL;
  32. 	}
  33. }*root;
  34. void insert(string str,int len)
  35. {
  36. 	node *curr=root;
  37. 	int id;
  38. 	for(int i=0;i<len;i++)
  39. 	{
  40. 		if(str[i]>='a'&&str[i]<='z')
  41. 		    id=str[i]-'a';
  42. 		else if(str[i]>='A'&&str[i]<='Z')
  43. 		    id=str[i]-'A'+25;
  44. 		if(curr->next[id]==NULL) 
  45. 			curr->next[id]=new node();
  46. 		curr=curr->next[id];
  47. 	}
  48. 	curr->endmark=curr->endmark+1;
  49.  
  50. }
  51. int search(string str,int len)
  52. {
  53. 	node *curr=root;
  54. 	int id;
  55. 	for(int i=0;i<len;i++)
  56. 	{
  57. 		if(str[i]>='a'&&str[i]<='z')
  58. 		    id=str[i]-'a';
  59. 		else if(str[i]>='A'&&str[i]<='Z')
  60. 		    id=str[i]-'A'+25;
  61. 		if(curr->next[id]==NULL) return 0;
  62. 		curr=curr->next[id];
  63. 	}
  64. 	return curr->endmark;
  65. }
  66. void del(node *cur)
  67. {        
  68.       for(int i=0;i<51;i++)
  69.              if(cur->next[i])
  70.                   del(cur->next[i]) ;     
  71.       delete(cur) ;
  72. }
  73. int main()
  74. {
  75. 	//freopen("input.txt","r",stdin);
  76. 	//freopen("output.txt","w",stdout);
  77. int num_word,i,t,ca=1,l;
  78. string str,s2;
  79. cin>>t;
  80. while(t--)
  81. {
  82. root=new node();
  83. cin>>num_word;
  84. for(i=0;i<num_word;i++)
  85. {
  86. 	cin>>str;
  87. 	l=str.size();
  88. 	if(l>3)
  89. 		sort(str.begin()+1,str.end()-1);
  90. 	insert(str,l);
  91. 	str="";
  92. }
  93. 	int query,ans=1,ll,jj;
  94. 	char s1[100005];
  95. 	cin>>query;
  96. 	printf("Case %d:\n",ca++);
  97. 	getchar();
  98. 	for(jj=1;jj<=query;jj++)
  99. 	{
  100. 		ans=1;
  101. 		gets(s1);
  102. 		str=s1;
  103. 		ll=str.size();
  104. 		i=0;
  105. 		while(i<ll)
  106. 		{
  107. 			s2="";
  108. 			while(i<ll&&str[i]!=' ')
  109. 			{
  110. 				s2=s2+str[i++];
  111. 			}
  112. 			while(str[i]==' '&&i<ll) 
  113. 				i++;
  114.  
  115. 			l=s2.size();
  116. 			if(l==0) {ans*=1; continue;}
  117. 	if(l>3)
  118. 		sort(s2.begin()+1,s2.end()-1);
  119. 	ans*=search(s2,s2.size());
  120. 		}
  121. 	printf("%d\n",ans);
  122. 	}
  123. 	del(root);
  124. }
  125. 	return 0;
  126. }
Success #stdin #stdout 0s 3456KB
comments (?)
stdin 
16
8
baggers
beggars
in
the
blowed
bowled
barn
bran
1
beggars bowled in the barn
3
a
b
c
1
a b c
2
a
b
1
a b c
3
abczzz
AbcdZZ
lfdpPSlslaSPApSWlwLWWWsssss
3
abcdef

AZbcdZ abczzz lfdpPSlslaSPApSWlwLWWWsssss lfdpPSlslaSAPpSWlwLWWWsssss 
3
abcd
acbd
xyz
2
      
abcd xyz
3
abcd
acbd
xyz
3
              
        a     afdd hghnh
abcd xyz
2
BD
Sle
2
N
 Sle
2
abc
gbc
3
abc abc abc
gbc gbc gbc
abc gbc
8
baggers
beggars
in
the
blowed
bowled
barn
bran
1
beggars bowled in the barn
3
a
b
c
1
a b c
2
a
b
1
a b c
3
abczzz
AbcdZZ
lfdpPSlslaSPApSWlwLWWWsssss
3
abcdef

AZbcdZ abczzz lfdpPSlslaSPApSWlwLWWWsssss lfdpPSlslaSAPpSWlwLWWWsssss 
3
abcd
acbd
xyz
2
      
abcd xyz
3
abcd
acbd
xyz
3
              
        a     afdd hghnh
abcd xyz
2
BD
Sle
2
N
 Sle
2
abc
gbc
3
abc abc abc
gbc gbc gbc
abc gbc
stdout 
Case 1:
8
Case 2:
1
Case 3:
0
Case 4:
0
1
1
Case 5:
1
2
Case 6:
1
0
2
Case 7:
0
1
Case 8:
1
1
1
Case 9:
8
Case 10:
1
Case 11:
0
Case 12:
0
1
1
Case 13:
1
2
Case 14:
1
0
2
Case 15:
0
1
Case 16:
1
1
1
https://ideone.com/DOL9mU
language:
C++ (gcc 8.3)
created:
12 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!