fork download
copy 
  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. 	int next[52+1];
  28. 	node()
  29. 	{
  30. 		endmark=0;
  31. 		for(int i=0;i<53;i++) next[i]=-1;
  32. 	}
  33. }*root,nodes[110000];
  34. int allocated_nodes;
  35. node* alloc(){
  36. 	if(allocated_nodes == sizeof(nodes)/sizeof(nodes[0]))
  37. 		exit(123);
  38. 	node *n = nodes + allocated_nodes++;
  39. 	*n = node();
  40. 	return n;
  41. }
  42. void insert(string str,int len)
  43. {
  44. 	node *curr=root;
  45. 	int id;
  46. 	for(int i=0;i<len;i++)
  47. 	{
  48. 		if(str[i]>='a'&&str[i]<='z')
  49. 		    id=str[i]-'a';
  50. 		else if(str[i]>='A'&&str[i]<='Z')
  51. 		    id=str[i]-'A'+26;
  52. 		if(curr->next[id]==-1) 
  53. 			curr->next[id]=alloc()-nodes;
  54. 		curr=nodes+curr->next[id];
  55. 	}
  56. 	curr->endmark=curr->endmark+1;
  57.  
  58. }
  59. int search(string str,int len)
  60. {
  61. 	node *curr=root;
  62. 	int id;
  63. 	for(int i=0;i<len;i++)
  64. 	{
  65. 		if(str[i]>='a'&&str[i]<='z')
  66. 		    id=str[i]-'a';
  67. 		else if(str[i]>='A'&&str[i]<='Z')
  68. 		    id=str[i]-'A'+26;
  69. 		if(curr->next[id]==-1) return 0;
  70. 		curr=nodes+curr->next[id];
  71. 	}
  72. 	return curr->endmark;
  73. }
  74. int main()
  75. {
  76. 	//freopen("input.txt","r",stdin);
  77. 	//freopen("output.txt","w",stdout);
  78. int num_word,i,t,ca=1,l;
  79. string str,s2;
  80. cin>>t;
  81. while(t--)
  82. {
  83. 	allocated_nodes = 0;
  84. root=alloc();
  85. cin>>num_word;
  86. for(i=0;i<num_word;i++)
  87. {
  88. 	cin>>str;
  89. 	l=str.size();
  90. 	if(l>3)
  91. 		sort(str.begin()+1,str.end()-1);
  92. 	insert(str,l);
  93. 	str="";
  94. }
  95. 	int query,ans=1,ll,jj;
  96. 	char s1[100005];
  97. 	cin>>query;
  98. 	printf("Case %d:\n",ca++);
  99. 	getchar();
  100. 	for(jj=1;jj<=query;jj++)
  101. 	{
  102. 		ans=1;
  103. 		gets(s1);
  104. 		str=s1;
  105. 		ll=str.size();
  106. 		i=0;
  107. 		while(i<ll)
  108. 		{
  109. 			s2="";
  110. 			while(i<ll&&str[i]!=' ')
  111. 			{
  112. 				s2=s2+str[i++];
  113. 			}
  114. 			while(str[i]==' '&&i<ll) 
  115. 				i++;
  116.  
  117. 			l=s2.size();
  118. 			if(l==0) {ans*=1; continue;}
  119. 	if(l>3)
  120. 		sort(s2.begin()+1,s2.end()-1);
  121. 	ans*=search(s2,s2.size());
  122. 		}
  123. 	printf("%d\n",ans);
  124. 	}
  125. }
  126. 	return 0;
  127. }
Success #stdin #stdout 0.02s 26656KB
comments (?)
stdin
copy 
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
copy 
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/jUMehM
language:
C++ (gcc 8.3)
created:
10 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!