fork download 
  1. /*
  2.  * BDFHJK
  3.  * Sun, 17 Apr 2011 11:40:24 +0200
  4.  */
  5.  
  6.  
  7. #include<string>
  8. #include<list>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<queue>
  13. #include<stack>
  14. #include<utility>
  15. #include<sstream>
  16. #include<cstring>
  17. #include<cmath>
  18. #include<cstdlib>
  19. #include<algorithm>
  20. #include<vector>
  21. #include<cstdio>
  22. #include<iostream>
  23.  
  24. using namespace std;
  25.  
  26. //#define DEBUG 1
  27. #define FOR(I,A,B) for(int I=(A);I<=(B);I++)
  28. #define REP(I,N) for(int I=0;I<(N);I++)
  29. #define ALL(X) (X).begin(),(X).end()
  30. #define FORD(I,A,B) for(int I=(A);I>=(B);I--)
  31. #define INF ((int)1e9)
  32. #define VAR(V,init) __typeof(init) V=(init)
  33. #define FOREACH(I,C) for(VAR(I,(C).begin());I!=(C).end();I++)
  34. #define PB push_back
  35. #define MP make_pair
  36. #define FI first
  37. #define SE second
  38. #define MOD ((int)1e9+7)
  39. typedef vector<int> VI;
  40. typedef pair<int,int> PII;
  41. typedef long long LL;
  42. typedef vector<string> VS;
  43.  
  44. LL nwd(LL a, LL b) { return !b?a:nwd(b,a%b); }
  45.  
  46. int t, N, K;
  47.  
  48. string SJ[((int)1e5+7)];  
  49. string SP[((int)1e5+7)];
  50. int W[((int)1e5+7)];
  51.  
  52.  
  53. void licz(int l, int p)
  54. {
  55. 	vector<pair<string, int> > PO;
  56. 	vector<string> SJV;
  57.  
  58. 	REP(i, N) 
  59. 	{
  60. 		//Słowo musi mieć przynajmniej l+p znaków
  61. 		if (SJ[i].size() >= l+p) 
  62. 		{
  63. 			string temp = "";
  64. 			REP(j, l) temp+=SJ[i][j];
  65. 			REP(j, p) temp+=SJ[i][SJ[i].size()-(p-j)];
  66. 			SJV.push_back(temp);
  67. 			#ifdef DEBUG
  68. 			cout << "SJIN: " << temp << endl;
  69. 			#endif
  70. 		}
  71. 	}
  72. 	stable_sort(SJV.begin(), SJV.end());
  73.  
  74. 	REP(i, K)
  75. 	{
  76. 		if(SP[i].size() == p+l+1)
  77. 		{
  78. 			int lzl=0;
  79. 			while(SP[i][lzl] != '*')lzl++;
  80. 			int pzl= SP[i].size() - lzl - 1;
  81. 			if (lzl != l || pzl != p) continue;
  82. 			string temp = SP[i];
  83. 			temp.erase(lzl,1);
  84. 			PO.PB(MP(temp, i));
  85. 			#ifdef DEBUG
  86. 			cout << "SPIN" << i << " " << " " << temp << endl;
  87. 			#endif
  88. 		}
  89. 	}
  90.  
  91. 	vector<string>::iterator low, up;
  92.  
  93. 	REP(i, PO.size())
  94. 	{
  95. 		low = lower_bound(ALL(SJV), PO[i].FI);
  96. 		up = upper_bound(ALL(SJV), PO[i].FI);
  97. 		W[PO[i].SE] = int (up-low);
  98. 		#ifdef DEBUG
  99. 		printf("W[%d] = %d\n", PO[i].SE, W[PO[i].SE]);
  100. 		#endif
  101. 	}
  102. } 
  103.  
  104.  
  105.  
  106. int main()
  107. {
  108. 	scanf("%d\n", &t);
  109. 	REP(zi, t)
  110. 	{
  111. 		scanf("%d\n", &N); 
  112. 		REP(i, N) cin >> SJ[i];
  113. 		scanf("%d\n", &K);
  114. 		REP(i, K) cin >> SP[i];
  115.  
  116. 		sort(SJ, SJ+N);
  117.  
  118. 		//i - liczba znaków przed gwiazdką, j - liczba znaków po gwiazdce
  119. 		REP(i, 10) REP(j, 10) licz(i, j);
  120.  
  121. 		REP(i, K) printf("%d\n", W[i]);
  122. 	}
  123. }
stdin 
1
5
zupa
z
malpy
intruz
pyszny
3
z*
m*y
g*ingo
compilation info 
prog.cpp: In function ‘void licz(int, int)’:
prog.cpp:61: warning: comparison between signed and unsigned integer expressions
prog.cpp:76: warning: comparison between signed and unsigned integer expressions
prog.cpp:93: warning: comparison between signed and unsigned integer expressions
prog.cpp: In function ‘int main()’:
prog.cpp:108: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:111: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:113: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout 
2
1
0
https://ideone.com/XLcDf
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!