fork download
copy 
  1. // author : Nguyễn Trọng Nguyễn - ITK22 NBK
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ii pair <int, int>
  7. #define fi first
  8. #define sc second
  9.  
  10. const int maxn = (int)1e5;
  11. const int maxsize = (int)3e6;
  12. const int base = 31;
  13.  
  14. const int mod = (int)1e9 + 7;
  15. const int mod2 = 111539786;
  16.  
  17. int n, q;
  18. int sz[maxn + 5];
  19. string a[maxn + 5];
  20. int POW[maxsize + 5];
  21.  
  22. void init () {
  23. 	cin >> n >> q;
  24. 	for (int i = 1; i <= n; i++) {
  25. 		cin >> a[i];
  26. 		sz[i] = a[i].size();
  27. 		a[i] = ' ' + a[i];	
  28. 	}
  29. }
  30.  
  31. ii get (string s, int l, int r) {
  32. 	int h1 = 0, h2 = 0;
  33. 	for (int i = l; i <= r; i++)
  34. 		h1 = (h1 * base + s[i] - 'a' + 1) % mod;
  35. 	for (int i = l; i <= r; i++)
  36. 		h2 = (h2 * base + s[i] - 'a' + 1) % mod2;
  37. 	return {h1, h2};
  38. }
  39.  
  40. void process () {
  41. 	if (n > 1000 or q > 1000) return ;
  42.  
  43. 	vector <int> ans;
  44.  
  45. 	POW[0] = 1;
  46. 	for (int i = 1; i <= maxsize; i++)
  47. 		POW[i] = POW[i - 1] * base % mod;
  48.  
  49. 	for (int k = 1; k <= q; k++) {
  50. 		string s; cin >> s;
  51. 		int len = s.size();
  52. 		s = ' ' + s;
  53.  
  54. 		int cnt = 0, pos = s.find("*");
  55.  
  56. 		ii Hash1 = get(s, 1, pos - 1);
  57. 		ii Hash2 = get(s, pos + 1, len);
  58.  
  59. 		for (int i = 1; i <= n; i++) {
  60. 			if (sz[i] + 1 < len) continue;
  61.  
  62. 			ii Hash3 = get(a[i], 1, pos - 1);
  63. 			ii Hash4 = get(a[i], sz[i] - len + pos + 1, sz[i]);
  64.  
  65. 			if (Hash1 == Hash3 and Hash2 == Hash4)
  66. 				cnt++;
  67. 		}
  68.  
  69. 		ans.push_back(cnt);
  70. 	}
  71.  
  72. 	for (int i = 1; i <= q; i++) {
  73. 		int x; cin >> x;
  74. 		if (x != ans[i - 1]) {
  75. 			cout << "WA";
  76. 			return ;
  77. 		}
  78. 	}
  79.  
  80. 	cout << "AC";
  81. }
  82.  
  83. signed main () {
  84. 	cin.tie(0)->sync_with_stdio(false);
  85.  
  86. 	#ifndef ONLINE_JUDGE
  87. 	freopen("test.inp","r",stdin);
  88. 	freopen("test.out","w",stdout);
  89. 	#endif
  90.  
  91. 	init();
  92. 	process();
  93.  
  94. 	return 0;
  95. }
Success #stdin #stdout 0.02s 30156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
AC
https://ideone.com/jgOj26
language:
C++14 (gcc 8.3)
created:
6 days 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!