fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5.  
  6.  
  7. const int M = 1000000007;
  8. const int N = 3e5+9;
  9. const int INF = 2e9+1;
  10. const int MAXN = 100000;
  11. const int LINF = 2000000000000000001;
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15.  
  16.  
  17. vector<int> a;
  18.  
  19.  
  20. //* Template1 for Atleast k (i.e. >= k )
  21.  
  22. //* 	We Start with Invalid window
  23. //* 	Keep expanding Invalid window till it becomes valid
  24. //* 	Once it's Valid 
  25. //*         Keep shrinking till it's valid (i.e. becomes invalid)
  26. //*         Also keep Computing result
  27.  
  28.  
  29.  
  30. void consistency1(string str, string t){
  31. 	int n = str.size();
  32. 	int m = t.size();
  33.  
  34. 	unordered_map<char, int> mp;
  35. 	for(int i=0; i<m; i++){
  36. 		mp[t[i]]++;
  37. 	}
  38.  
  39. 	int s = 0, e = 0;
  40. 	int minLen = n+1;
  41. 	int x = -1;
  42.  
  43. 	while(e<n){
  44. 	    //* Calculate State
  45. 	    if(mp.count(str[e])) mp[str[e]]--;
  46.  
  47. 	    bool isValid = true;
  48. 		for(auto& it : mp){
  49. 			if(it.second > 0){
  50. 				isValid = false;
  51. 				break;
  52. 			}
  53. 		}
  54.  
  55. 	    //* Invalid window => keep expanding
  56. 	    if(!isValid){
  57. 	        e++;
  58. 	    }
  59. 	    else{
  60. 	        //* Valid window => keep shrinking && Computing Result
  61. 	        while(s<=e){
  62. 	        	bool isValid = true;
  63. 	        	for(auto& it : mp){
  64. 	        		if(it.second > 0){
  65. 	        			isValid = false;
  66. 	        			break;
  67. 	        		}
  68. 	        	}
  69. 	        	if(!isValid) break;
  70. 				int len = e-s+1;
  71. 				if(len < minLen){
  72. 					minLen = len;
  73. 					x = s;
  74. 				}
  75. 			    if(mp.count(str[s])) mp[str[s]]++;
  76. 	            s++;
  77. 	        }
  78. 	        e++;
  79. 	    }
  80. 	}
  81.  
  82. 	if(x==-1){
  83. 		cout << "-1" << endl;
  84. 		return;
  85. 	}
  86. 	string ans = str.substr(x, minLen);
  87. 	cout << ans << endl;
  88.  
  89. }
  90.  
  91.  
  92.  
  93.  
  94. //* Template2 for Atleast k (i.e. >= k )
  95. //* 	(based on Cache Invalidation) 
  96.  
  97. //* 	We Start with Invalid window
  98. //* 	If Window is valid 
  99. //* 		Keep shrinking till it's valid (i.e. becomes invalid)
  100. //* 		Also keep Computing result
  101. //* 	(similar to Cache Invalidation)
  102.  
  103.  
  104. void consistency2(string str, string t){
  105. 	int n = str.size();
  106. 	int m = t.size();
  107.  
  108. 	unordered_map<char, int> mp;
  109. 	for(int i=0; i<m; i++){
  110. 		mp[t[i]]++;
  111. 	}
  112. 	int s = 0, e = 0;
  113. 	int minLen = n+1;
  114. 	int x = -1;
  115.  
  116. 	while(e<n){
  117. 	    //* Calculate State
  118. 	    if(mp.count(str[e])) mp[str[e]]--;
  119.  
  120. 	    //* Valid window => keep shrinking && Computing Result
  121. 		while(s<=e){
  122. 			bool isValid = true;
  123. 			for(auto& it : mp){
  124. 				if(it.second > 0){
  125. 					isValid = false;
  126. 					break;
  127. 				}
  128. 			}
  129. 			if(!isValid) break;
  130. 			int len = e-s+1;
  131. 			if(len < minLen){
  132. 				minLen = len;
  133. 				x = s;
  134. 			}
  135. 		    if(mp.count(str[s])) mp[str[s]]++;
  136. 		    s++;
  137. 		}
  138.  
  139. 		//* Invalid window => Expand 
  140. 		e++;
  141. 	}
  142.  
  143. 	if(x==-1){
  144. 		cout << "-1" << endl;
  145. 		return;
  146. 	}
  147. 	string ans = str.substr(x, minLen);
  148. 	cout << ans << endl;
  149.  
  150. }
  151.  
  152.  
  153. void solve() {
  154.  
  155. 	string str, t;
  156. 	cin >> str >> t;
  157.  
  158. 	consistency1(str, t);
  159. 	consistency2(str, t);
  160.  
  161. }
  162.  
  163.  
  164.  
  165.  
  166.  
  167. int32_t main() {
  168.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  169.  
  170.     int t = 1;
  171.     cin >> t;
  172.     while (t--) {
  173.         solve();
  174.     }
  175.  
  176.     return 0;
  177. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4
abc ac
a b
a aa
ADOBECODEBANC ABC
stdout
copy 
abc
abc
-1
-1
-1
-1
BANC
BANC
https://ideone.com/BtIolc
language:
C++14 (gcc 8.3)
created:
1 day 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!