fork(2) download
copy 
  1. /*************** Author: sambit1993 ******************/
  2. /* 	Category: UpdateLater          */
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <vector>
  9. #include <list>
  10. #include <string>
  11. #include <set>
  12. #include <queue>
  13. #include <ctime>
  14. #include <fstream>
  15. #include <sstream>
  16. #include <cmath>
  17. #include <limits>
  18. #include <climits>
  19. #include <bitset>
  20. #include <iomanip>
  21. #include <stack>
  22.  
  23. #ifndef ONLINE_JUDGE
  24. 	#define gc getchar
  25. #else
  26. 	#define gc getchar_unlocked
  27. #endif
  28.  
  29. #define s(x) scanf("%d",&x)
  30. #define sil(x) scanf("%llu",&x)
  31. #define sd(x) scanf("%ld",&x)
  32.  
  33. #define ri(x) x=read<int>()
  34. #define rl(x) x=read<ll>()
  35. #define ru(x) x=read<ull>() 
  36.  
  37. #define FOR(i,a,b) for( int i=(a); i<(b); ++i)               // exclusive for
  38. #define FORR(i,a,b) for( int  i=(a-1) ; i>=(b); --i)
  39. #define REP(k,a,b) for(int  k=(a); k <= (b); ++k)			// inclusive for
  40. #define REPR(i,a,b) for( int i=(a) ; i>=(b); --i)
  41. #define ALL(c) (c).begin(), (c).end()  
  42. #define PB push_back 
  43. #define MP make_pair 
  44. #define SZ(x) ((int)((x).size()))
  45. #define SRT(v) std::sort(ALL(v))
  46. #define CTN(x) std::cout<<x<<'\n'								//cout with newline
  47. #define CTS(x) std::cout<<x<<" "                                //cout with space
  48. #define CLR(x) std::memset(x,0,sizeof(x))
  49. #define FILL(x,n) std::fill_n(x,sizeof(x),n)
  50. #define T(t) int t; ri(t); while(t--) 
  51. #define DBGA(x,n) {for(int i=0;i<n;i++) cerr<<x[i]<<" "; cerr<<"\n";}
  52. #define REC(x) clock_t x=clock()
  53. #define CPS CLOCKS_PER_SEC 
  54. #define TM(x,y) CTN(((double)(y-x)/CPS))
  55. #define abs(x) ((x)>0?(x):(-(x)))
  56.  
  57.  
  58. typedef std::vector<int> VI;
  59. typedef std::vector<long long int> VL;
  60. typedef std::vector<std::string> VS;
  61.  
  62. typedef std::pair<int,int> PII;
  63. typedef unsigned long long ull;
  64. typedef long long ll;
  65.  
  66. template <typename T>
  67. inline T read()
  68. {
  69. 	register T x=0;
  70. 	register char c;
  71. 	while((c=gc())<48 || c>'9');
  72. 	x=c-'0';
  73. 	while((c=gc())>='0' && c<='9')
  74. 		x=(x<<3)+(x<<1)+c-'0';
  75. 	return x;
  76. }
  77. using namespace std;
  78. /**************************GLOBAL DATA***************************************/
  79. int P[20][500000];
  80. struct node
  81. {
  82. 	int s_ind,next_s_ind;
  83. 	int ind;
  84. }elem[500000];
  85. PII ud[250000];
  86. int log_n;
  87. VI two,one;
  88. /**************************GLOBAL DATA***************************************/
  89. int lower(VI &one,int p)
  90. {
  91. 	int low=0,up=SZ(one)-1,ans=-1;
  92. 	while(low<=up)
  93. 	{
  94. 		int mid=((low+up)>>1);
  95. 		if(one[mid]>p)
  96. 		{
  97. 			up=mid-1;
  98. 		}
  99. 		else
  100. 		{
  101. 				low=mid+1;
  102. 				ans=mid;
  103. 		}
  104. 	}
  105. 	return ans;
  106.  
  107. }
  108. int upper(VI &one,int p)
  109. {
  110. 	int low=0,up=SZ(one)-1,ans=-1;
  111. 	while(low<=up)
  112. 	{
  113. 		int mid=((low+up)>>1);
  114. 		if(one[mid]<p)
  115. 		{
  116. 			low=mid+1;
  117. 		}
  118. 		else
  119. 		{
  120. 				up=mid-1;
  121. 				ans=mid;
  122. 		}
  123. 	}
  124. 	return ans;
  125.  
  126. }
  127.  
  128. int lcp(int i,int j,int n)
  129. {
  130. 	int ans=0;
  131.  
  132. 	for(int k=log_n;k>=0 && i<n && j<n ; k--)
  133. 	{
  134. 		if(P[k][i]==P[k][j])
  135. 		{
  136. 			ans+=(1<<k);
  137. 			i+=(1<<k);
  138. 			j+=(1<<k);
  139. 		}
  140. 	}
  141. 	return ans;
  142. }
  143. bool cmp(node a,node b)
  144. {
  145. 	return a.s_ind==b.s_ind?a.next_s_ind<b.next_s_ind:a.s_ind<b.s_ind;
  146. }
  147. int main()
  148. {
  149. 	std::ios_base::sync_with_stdio(false);
  150. 	#ifndef ONLINE_JUDGE
  151. 		freopen("in.txt","r",stdin);
  152. 	#endif
  153.  
  154. 	string s1,s2;
  155. 	cin>>s1>>s2;
  156. 	string s=s1+s2;
  157. 	FOR(i,0,SZ(s))
  158. 		P[0][i]=s[i]-'a';
  159. 	int stp=1,cnt=1;
  160. 	int n=SZ(s);
  161. 	for(;cnt<n;stp++,cnt*=2)
  162. 	{
  163.  
  164. 		FOR(i,0,n)
  165. 		{
  166. 			elem[i].s_ind=P[stp-1][i];
  167. 			elem[i].next_s_ind=i+cnt<n?P[stp-1][i+cnt]:-1;
  168. 			elem[i].ind=i;
  169. 		}
  170. 		sort(elem,elem+n,cmp);
  171. 		FOR(i,0,n)
  172. 			{
  173.  
  174. 				P[stp][elem[i].ind]=i> 0 && elem[i].s_ind==elem[i-1].s_ind && elem[i].next_s_ind == elem[i- 1].next_s_ind ? P[stp][elem[i-1].ind] : i;
  175. 			}
  176. 	}
  177. 	FOR(i,0,n)
  178. 	{
  179. 		if(elem[i].ind>=SZ(s1)) two.PB(i);
  180. 			else one.PB(i);
  181. 	}
  182. 	log_n=stp-1;
  183. 	/*FOR(i,0,n)
  184. 	{
  185. 		cout<<elem[i].ind<<endl;
  186. 	} */
  187. 	int index=-1,mx_len=-1;
  188. 	FOR(i,0,SZ(s2))
  189. 	{
  190. 		ud[i].first=lower(one,two[i]); 
  191. 		ud[i].second=upper(one,two[i]); 
  192. 	}
  193. 	/*FOR(i,0,SZ(one))
  194. 	 cout<<one[i]<<endl;
  195. 	CTN(" ");
  196. 	FOR(i,0,SZ(two))
  197. 		cout<<two[i]<<endl;
  198. 	CTN(" ");*/
  199.  
  200. 	FOR(i,0,SZ(s2))
  201. 	{
  202.  
  203. 		int tmp_len1=-1,tmp_len2=-1;
  204. 		if(ud[i].first!=-1)
  205. 			tmp_len1=lcp(elem[two[i]].ind,elem[one[ud[i].first]].ind,n);
  206. 		if(ud[i].second!=-1)
  207. 			tmp_len2=lcp(elem[two[i]].ind,elem[one[ud[i].second]].ind,n);
  208. 		if(tmp_len1>0 && (tmp_len1>mx_len || (tmp_len1==mx_len && elem[two[i]].ind<=index)))
  209. 		{
  210. 			mx_len=tmp_len1;
  211. 			index=elem[two[i]].ind;
  212. 		}
  213. 		if(tmp_len2>0 && (tmp_len2>mx_len || (tmp_len2==mx_len && elem[two[i]].ind<=index)))
  214. 		{
  215. 			mx_len=tmp_len2;
  216. 			index=elem[two[i]].ind;
  217. 		}
  218. 		//if(mx_len==7) cout<<"7 "<<two[i]<<" "<<elem[one[ud[i].second]].ind<<endl;
  219. 		//cout<<i<<" "<<ud[i].first<<" "<<ud[i].second<<endl;
  220. 	}
  221. /*	int _i=1,_j=2;
  222. 	cout<<log_n<<endl;
  223. 	REPR(k,log_n,0)
  224. 	{
  225. 		if(P[k][_i]==P[k][_j])
  226. 		{
  227. 			cout<<_i<<" "<<_j<<" "<<P[k][_i]<<endl;
  228. 			_i+=(1<<k);
  229. 			_j+=(1<<k);
  230. 		}
  231. 	}*/
  232.  
  233.  
  234. 	if(index!=-1){ cout<<s2.substr(index-SZ(s1),mx_len)<<"\n"; }
  235. 	index!=-1?cout<<mx_len<<"\n":cout<<"0\n";
  236.  
  237. }
Success #stdin #stdout 0s 50312KB
comments (?)
stdin
copy 
fhfgfg
fagehg
stdout
copy 
f
1
https://ideone.com/KK1rak
language:
C++ (gcc 8.3)
created:
10 years 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!