fork download
copy 
  1. //============================================================================
  2. // Name        : 
  3. // Author      : Atul Kumar Gupta
  4. // Description : 
  5. // Status	   : AC
  6. //============================================================================
  7.  
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define mod 1000000007
  13. #define dg(x) cout << '>' << #x << ':' << x << endl;
  14. #define sz(c)  (int) c.size()
  15. #define all(c) c.begin(), c.end()
  16. #define tr(container,it) for(__typeof(container.begin()) it = container.begin();it != container.end(); it++)
  17. #define present(s,x) s.find(x) != s.end()
  18. #define cpresent(c,x) find(all(c),x) != c.end()
  19. #define pb push_back
  20. #define mp make_pair
  21. #define ff first
  22. #define ss second
  23. #define rep(i,n) for(int i=0;i<n;i++)
  24. #define dep(i,n) for(int i=n-1;i>=0;i--)
  25. #define repn(i,a,b) for(int i=a; i<b;i++)
  26. #define ini(n) scanf("%d",&n)
  27. #define ind(n,m) scanf("%d %d",&n,&m);
  28. #define inl(n) scanf("%l64d",&n)
  29. #define ins(n) scanf("%s",n);
  30. #define opi(n) printf("%d",n)
  31. #define opl(n) printf("%l64d",n)
  32. #define ops(n) printf("%s",n)
  33. #define opn printf("\n")
  34. #define opsp printf(" ");
  35. #define opa(n) cout<<n
  36.  
  37. //#define TRACE
  38.  
  39. #ifdef TRACE
  40. #define trace1(x)                cerr << #x << ": " << x << endl;
  41. #define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  42. #define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  43. #define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  44. #define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  45. #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  46.  
  47. #else
  48.  
  49. #define trace1(x)
  50. #define trace2(x, y)
  51. #define trace3(x, y, z)
  52. #define trace4(a, b, c, d)    
  53. #define trace5(a, b, c, d, e)
  54. #define trace6(a, b, c, d, e, f)
  55.  
  56. #endif 
  57.  
  58. typedef pair<int,int> pi;
  59. typedef vector<pi> vp;
  60. typedef vector<vp> vvp;
  61. typedef vector<int> vi;
  62. typedef unsigned long long int ull;
  63. typedef long long int ll;
  64. typedef vector<ll> vl;
  65. typedef vector< vi > vvi;
  66. typedef priority_queue<int> pq;
  67. typedef priority_queue<int, vi , greater<int> >minpq;
  68. typedef priority_queue<pi,vp,greater<pi> > mpq;
  69.  
  70. //Euclidean GCD
  71. //------------------------------------------
  72. //============================================================================
  73. int gcd(int A, int B) {
  74.     if(B==0)
  75.         return A;
  76.     else
  77.         return gcd(B, A % B);
  78. }
  79. //Fermat MMI
  80. //------------------------------------------
  81. //============================================================================
  82. //a^n % m
  83. ll mod_exponentiation(ll base, ll exponent, int modulus)
  84. {
  85.     ll result = 1;
  86.     while (exponent > 0)
  87.     {
  88.         if (exponent % 2 == 1)
  89.             result = (result * base) % modulus;
  90.         exponent = exponent >> 1;
  91.         base = (base * base) % modulus;
  92.     }
  93.     return result;
  94. }
  95.  
  96. int fermat(ll n, ll m){
  97. 	return mod_exponentiation(n,m-2,m);
  98. }
  99.  
  100. struct node{
  101. 	int a;
  102. 	int cnt;
  103. };
  104. //custom comparator
  105. struct Compare{
  106. 	bool operator()(node &a, node &b){
  107. 		return a.cnt > b.cnt ;
  108. 	}
  109. };
  110.  
  111. //conversion
  112. //============================================================================
  113. //------------------------------------------
  114. inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
  115. template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
  116.  
  117. //math
  118. //-------------------------------------------
  119. //============================================================================
  120. template<class T> inline T sqr(T x) {return x*x;}
  121.  
  122.  
  123. //Main Starts
  124. //------------------------------------------
  125. //============================================================================
  126.  
  127. string a,b;
  128. vi pre,suf;
  129. bool flag =  false;
  130. void prefix(){
  131. 	int i=0,j=0;
  132. 	while(i<sz(a) and j<sz(b)){
  133. 		if(b[j] == a[i]){
  134. 			pre.pb(i);
  135. 			i++;
  136. 			j++;
  137.  
  138. 			flag = true;
  139. 		}
  140. 		else
  141. 			i++;
  142. 	}
  143. 	cout<<"prefix"<<endl;
  144. 	tr(pre,it){
  145. 		cout<<*it<<" "<<a[*it]<<endl;
  146. 	}
  147. }
  148. void suffix(){
  149. 	int i=sz(a)-1,j=sz(b)-1;
  150. 	while(i>=0 and j>=0){
  151. 		if(b[j] == a[i]){
  152. 			suf.pb(i);
  153. 			i--;
  154. 			j--;
  155.  
  156. 			flag = true;
  157. 		}
  158. 		else
  159. 			i--;
  160. 	}
  161. }
  162.  
  163. int main(){
  164. 	//ios_base::sync_with_stdio(false);cin.tie(NULL);
  165. 	cin>>a>>b;
  166. 	prefix();
  167. 	suffix();
  168. 	if(!flag){
  169. 		cout<<"-";
  170. 		return 0;
  171. 	}
  172. 	//trace2(a,b);
  173. 	sort(suf.begin() , suf.end());
  174. 	cout<<"suffix"<<endl;
  175. 	tr(suf,it){
  176. 		cout<<*it<<" "<<a[*it]<<endl;
  177. 	}
  178. 	int i1 =-1 , i2=sz(suf);
  179. 	int ans = 0;
  180. 	if(sz(pre) == 0){
  181. 		//cout<<"this  3 conditon is true\n";
  182. 		for(int i=0;i<sz(suf);i++)
  183. 			//if(suf[i]<sz(b))
  184. 			cout<<a[suf[i]];
  185. 		return 0; 
  186. 	}
  187. 	if(sz(suf) == 0){
  188. 		//cout<<"this 2 conditon is true\n";
  189. 		for(int i=0;i<sz(pre);i++)
  190. 			//if(pre[i]<sz(b))
  191. 			cout<<a[pre[i]];
  192. 		return 0; 
  193. 	}
  194.  
  195. 	else{
  196. 		//cout<<"this 4 conditon is true\n";
  197. 		int len=-1;
  198. 		for(int i=0;i<sz(pre);i++){
  199. 			auto it = upper_bound(suf.begin(),suf.end(),pre[i]);
  200. 			//trace1((sz(suf)-(it-suf.begin())));
  201. 			//trace1(i+1);
  202. 			len = i+1 + (sz(suf)-(it-suf.begin()));
  203. 			//trace1(len);
  204. 			if(len>ans){
  205. 				i1 = i;
  206. 				i2 = it-suf.begin();
  207. 				ans = len;
  208. 			}
  209. 		}
  210. 		//trace2(i1,i2);
  211. 		//trace1(ans);
  212. 		if(ans > sz(b)){
  213. 			//cout<<"this 5 conditon is true\n";
  214. 			for(int i=0;i<sz(b);i++)	
  215. 				cout<<b[i];
  216. 			return 0;
  217. 		}
  218. 		for(int i=0;i<=i1;i++){
  219. 			//if(pre[i]<sz(b))
  220. 			cout<<a[pre[i]];
  221. 		}
  222. 		for(int i=i2;i<sz(suf);i++){
  223. 			//sif(suf[i]<sz(b))
  224. 			cout<<a[suf[i]];
  225. 		}
  226. 	}
  227.  
  228.  
  229. }
  230.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
aaeojkdyuilpdvyewjfrftkpcobhcumwlaoiocbfdtvjkhgda
mlmarpivirqbxcyhyerjoxlslyfzftrylpjyouypvk


Codeforces test case 5
stdout
copy 
prefix
30 m
32 l
suffix
3 o
8 u
14 y
23 p
42 v
44 k
mlvk
https://ideone.com/fczWaU
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!