fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6.  
  7. using cd = std::complex<double>;
  8. const double PI = acos(-1);
  9.  
  10. /**
  11.  * Fast Fourier Transform - Optimized Implementation
  12.  * Transforms between coefficient and point-value representation
  13.  * Time: O(n log n), Space: O(n)
  14.  */
  15. void FFT(vector<cd> &coeff)
  16. {
  17. 	int n = coeff.size();
  18.  
  19. 	// Bit-reversal permutation - eliminates recursion overhead
  20. 	for (int i = 1, j = 0; i < n; i++)
  21. 	{
  22. 		int bit = n >> 1;
  23. 		for (; j & bit; bit >>= 1)
  24. 			j ^= bit;
  25. 		j ^= bit;
  26. 		if (i < j)
  27. 			swap(coeff[i], coeff[j]);
  28. 	}
  29.  
  30. 	// Iterative FFT with on-the-fly root computation
  31. 	for (int k = 1; k < n; k *= 2)
  32. 	{
  33. 		double ang = PI / k;
  34. 		cd wlen(cos(ang), sin(ang));
  35. 		for (int i = 0; i < n; i += 2 * k)
  36. 		{
  37. 			cd w(1);
  38. 			for (int j = 0; j < k; j++)
  39. 			{
  40. 				cd z = coeff[i + j + k] * w;
  41. 				coeff[i + j + k] = coeff[i + j] - z;
  42. 				coeff[i + j] += z;
  43. 				w *= wlen;
  44. 			}
  45. 		}
  46. 	}
  47. }
  48.  
  49. /**
  50.  * Convolution / Multiplication using optimized FFT
  51.  * Multiplies two vectors represented as double vectors
  52.  * Time: O(n log n), where n is the size of result
  53.  */
  54. template <typename T>
  55. vector<T> convolute(const vector<T> &a, const vector<T> &b)
  56. {
  57. 	if (a.empty() || b.empty())
  58. 		return {};
  59.  
  60. 	vector<T> res(a.size() + b.size() - 1);
  61. 	int L = 32 - __builtin_clz(res.size()), n = 1 << L;
  62. 	vector<cd> in(n), out(n);
  63.  
  64. 	// Convert template type to double for FFT
  65. 	for (int i = 0; i < a.size(); i++)
  66. 		in[i].real(static_cast<double>(a[i]));
  67. 	for (int i = 0; i < b.size(); i++)
  68. 		in[i].imag(static_cast<double>(b[i]));
  69.  
  70. 	FFT(in);
  71. 	for (cd &x : in)
  72. 		x *= x;
  73. 	for (int i = 0; i < n; i++)
  74. 		out[i] = in[-i & (n - 1)] - conj(in[i]);
  75. 	FFT(out);
  76.  
  77. 	// Convert back to template type with proper rounding
  78. 	for (int i = 0; i < res.size(); i++)
  79. 		res[i] = static_cast<T>(round(out[i].imag() / (4 * n)));
  80.  
  81. 	return res;
  82. }
  83.  
  84. template <typename T>
  85. vector<T> PolyModPow(vector<T> P, ll power)
  86. {
  87. 	vector<T> res{1};
  88. 	while (power)
  89. 	{
  90. 		if (power & 1)
  91. 			res = convolute(res, P);
  92. 		P = convolute(P, P);
  93. 		power >>= 1;
  94. 	}
  95. 	return res;
  96. }
  97.  
  98. int main()
  99. {
  100. 	ios_base::sync_with_stdio(false);
  101. 	cin.tie(nullptr);
  102. #ifndef ONLINE_JUDGE
  103. 	freopen("input.txt", "r", stdin);
  104. 	freopen("Output.txt", "w", stdout);
  105. #endif //! ONLINE_JUDGE
  106. 	int t = 1;
  107. 	ll N;
  108. 	// cin >> t;
  109. 	while (t--)
  110. 	{
  111. 		// Hash_t::pre(1 << 20);
  112. 		int n, m;
  113. 		string S, T;
  114. 		cin >> S >> T;
  115. 		n = S.length();
  116. 		m = T.length();
  117. 		vector<int> S1(n);
  118. 		for (int i = 0; i < n; i++)
  119. 		{
  120. 			if (S[i] == '*')
  121. 				S1[i] = 0;
  122. 			else
  123. 				S1[i] = (S[i] - 'a' + 1);
  124. 		}
  125.  
  126. 		vector<int> T1(m);
  127. 		for (int i = 0; i < m; i++)
  128. 		{
  129. 			if (T[i] == '*')
  130. 				T1[i] = 0;
  131. 			else
  132. 				T1[i] = (T[i] - 'a' + 1);
  133. 		}
  134. 		reverse(T1.begin(), T1.end());
  135.  
  136. 		vector<int> S2 = S1;
  137. 		vector<int> T2 = T1;
  138.  
  139. 		vector<int> S3 = S1;
  140. 		vector<int> T3 = T1;
  141.  
  142. 		auto square = [](vector<int> &v)
  143. 		{
  144. 			for (int i = 0; i < v.size(); i++)
  145. 				v[i] = v[i] * v[i];
  146. 		};
  147.  
  148. 		auto cube = [](vector<int> &v)
  149. 		{
  150. 			for (int i = 0; i < v.size(); i++)
  151. 				v[i] = v[i] * v[i] * v[i];
  152. 		};
  153.  
  154. 		square(S2);
  155. 		square(T2);
  156. 		cube(S3);
  157. 		cube(T3);
  158.  
  159. 		auto S3T1 = convolute(S3, T1);
  160. 		auto S2T2 = convolute(S2, T2);
  161. 		auto S1T3 = convolute(S1, T3);
  162.  
  163.  
  164. 		string ans("");
  165. 		for (int i = 0; i < n - m + 1; i++)
  166. 		{
  167. 			if (i + m - 1 > S3T1.size())
  168. 				break;
  169. 			if (i + m - 1 > S2T2.size())
  170. 				break;
  171. 			if (i + m - 1 > S1T3.size())
  172. 				break;
  173. 			int a = S3T1[i + m - 1];
  174. 			int b = S2T2[i + m - 1];
  175. 			int c = S1T3[i + m - 1];
  176. 			if (a - 2 * b + c == 0)
  177. 			{
  178. 				ans += "1";
  179. 			}
  180. 			else
  181. 				ans += "0";
  182. 		}
  183.  
  184. 		cout << ans << endl;
  185. 	}
  186. 	return 0;
  187. }
  188.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/6caI5n
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
7 hours 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!