fork download
copy 
  1. /*
  2. 	Author: Vo Minh Long
  3. 	Codeforces: mncuchiinhuttt
  4. 	CBT '25
  5. */
  6.  
  7. #include <iostream>
  8. #include <stdio.h>
  9. #include <time.h>
  10. #include <string.h>
  11. #include <assert.h>
  12. #include <math.h>
  13. #include <fstream>
  14. #include <algorithm>
  15. #include <vector>
  16. #include <queue>
  17. #include <map>
  18. #include <set>
  19. #include <stack>
  20. #include <unordered_map>
  21. #include <numeric>
  22. #include <functional>
  23. #include <bitset>
  24. #include <unordered_set>
  25.  
  26. using namespace std;
  27.  
  28. #include <ext/pb_ds/assoc_container.hpp>
  29. #include <ext/pb_ds/tree_policy.hpp>
  30. using namespace __gnu_pbds;
  31. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  32.  
  33. #define long        long long
  34.  
  35. #define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  36. #define yuri ios::sync_with_stdio(0);
  37. #define is cin.tie(0);
  38. #define dabet cout.tie(0);
  39. #define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  40. #define len(a) (int)(a.size())
  41. #define all(a) (a).begin(), (a).end()
  42.  
  43. const int N = 2e5 + 7;
  44. const int BASE = 307;
  45. const int INT_inf = 2e9;
  46. const long LL_inf = 9e18;
  47. const double eps = 1e-6;
  48. const short dx[] = {1, 0, -1, 0};
  49. const short dy[] = {0, 1, 0, -1};
  50. const pair<long, long> MOD = {1e9 + 7, 998244353};
  51.  
  52. template<typename T1, typename T2> bool maximize(T1& a, T2 b){if(a < b) return a = b, 1; return 0;}
  53. template<typename T1, typename T2> bool minimize(T1& a, T2 b){if(a > b) return a = b, 1; return 0;}
  54. template<typename T1> T1 abs(T1 a){return a < 0 ? -a : a;}
  55. template<typename T1> T1 sqr(T1 a){ return a * a; }
  56.  
  57. inline char getChar() { static char buf[1 << 16]; static size_t len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, sizeof(buf), stdin); return pos == len ? -1 : buf[pos++]; }
  58. inline int readInt() { char c; int ans = 0; while ((c = getChar()) < '0' or c > '9'); ans = c - '0'; while ((c = getChar()) >= '0' and c <= '9') ans = ans * 10 + c - '0'; return ans; }
  59.  
  60. int n, k, L, R, maxLen, ansID;
  61. int len[51];
  62. pair<long, long> pw[N], hashing[51][N];
  63. string s[51];
  64.  
  65. void setData();
  66. void solve();
  67.  
  68. int main()
  69. {
  70. 	setData();
  71. 	solve(); 
  72. }
  73.  
  74. inline pair<long, long> add(pair<long, long> a, pair<long, long> b)
  75. {
  76. 	return {(a.first + b.first) % MOD.first, (a.second + b.second) % MOD.second};
  77. }
  78.  
  79. inline pair<long, long> dash(pair<long, long> a)
  80. {
  81. 	return {(MOD.first - a.first) % MOD.first, (MOD.second - a.second) % MOD.second};
  82. }
  83.  
  84. inline pair<long, long> mul(pair<long, long> a, pair<long, long> b)
  85. {
  86. 	return {(a.first * b.first) % MOD.first, (a.second * b.second) % MOD.second};
  87. }
  88.  
  89. inline pair<long, long> get(int id, int l, int r)
  90. {
  91. 	return add(hashing[id][r], dash(mul(hashing[id][l - 1], pw[r - l + 1])));
  92. }
  93.  
  94. void setData()
  95. {
  96. 	yuri is dabet
  97. 	#define NAME "thuyvan"
  98. 	if (fopen(NAME".INP", "r"))
  99. 		freopen(NAME".INP", "r", stdin),
  100. 		freopen(NAME".OUT", "w", stdout);
  101. 	cin >> n >> k;
  102. 	pw[0] = {1, 1};
  103. 	for (int i = 1; i < N; ++i)
  104. 		pw[i] = mul(pw[i - 1], {BASE, BASE});
  105. 	for (int i = 0; i < n; ++i)
  106. 	{
  107. 		cin >> s[i];
  108. 		maximize(maxLen, len[i] = len(s[i]));
  109. 		for (int j = 0; j < len[i]; ++j)
  110. 			hashing[i][j + 1] = add(mul(hashing[i][j], {BASE, BASE}), {s[i][j], s[i][j]});
  111. 	}
  112. }
  113.  
  114. bool check(int len)
  115. {
  116. 	vector<pair<long, long> > hash;
  117. 	for (int i = 0; i < n; ++i)
  118. 	{
  119. 		vector<pair<long, long> > tmp;
  120. 		for (int j = 0; j + len <= ::len[i]; ++j)
  121. 			tmp.push_back(get(i, j + 1, j + len));
  122. 		sort(all(tmp));
  123. 		tmp.erase(unique(all(tmp)), tmp.end());
  124. 		for (const pair<long, long>& x : tmp)
  125. 			hash.push_back(x);
  126. 	}
  127. 	sort(all(hash));
  128. 	int maxLen = 0, cnt = 1;
  129. 	pair<long, long> hashKey = hash[0];
  130. 	for (int i = 1; i < len(hash); ++i)
  131. 	{
  132. 		if (hash[i] == hash[i - 1])
  133. 			++cnt;
  134. 		else
  135. 		{
  136. 			if (maximize(maxLen, cnt))
  137. 				hashKey = hash[i - 1];
  138. 			cnt = 1;
  139. 		}
  140. 	}
  141. 	if (maximize(maxLen, cnt))
  142. 		hashKey = hash[len(hash) - 1];
  143. 	if (maxLen < k)
  144. 		return 0;
  145. 	for (int i = 0; i < n; ++i)
  146. 		for (int j = 0; j + len <= ::len[i]; ++j)
  147. 			if (get(i, j + 1, j + len) == hashKey)
  148. 			{
  149. 				ansID = i;
  150. 				L = j;
  151. 				R = j + len - 1;
  152. 				return 1;
  153. 			}
  154. 	return 0;
  155. }
  156.  
  157. void solve()
  158. {
  159. 	for (int l = 1, r = maxLen; l <= r;)
  160. 	{
  161. 		int mid = (l + r) >> 1;
  162. 		if (check(mid))
  163. 			l = mid + 1;
  164. 		else 
  165. 			r = mid - 1;
  166. 	}
  167. 	for (int i = L; i <= R; ++i)
  168. 		cout << s[ansID][i];
  169. }
  170.  
  171. /* Some notes:
  172.  
  173. */
  174.  
Success #stdin #stdout 0.01s 7000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/16I3nk
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

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