fork download
copy 
  1. /*
  2. --------------------------------DO NOT COPY I REQUEST YOU PLEASE--------------------------
  3.  
  4. AUTHOR : Chandan Agrawal
  5. College : Poornima College of Engg. jaipur, Raj
  6. Mail : chandanagrawal23@gmail.com
  7.  
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. #include<stdio.h>
  12. using namespace std;
  13.  
  14. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define MAX 100050
  16.  
  17. #define ll long long
  18. #define ld long double
  19. #define lli long int
  20.  
  21. #define pb emplace_back
  22. #define INF 1000000000
  23. #define mod 1000000007
  24. #define MOD 1000000007
  25.  
  26. // trignometric function always give value in Radians only
  27. #define PI acos(-1) //3.1415926535897932384626433832795028
  28. #define dsin(degree) sin(degree*(PI/180.0))
  29. #define dcos(degree) cos(degree*(PI/180.0))
  30. #define dtan(degree) tan(degree*(PI/180.0))
  31.  
  32. #define rsin(radian) sin(radian)
  33. #define rcos(radian) cos(radian)
  34. #define rtan(radian) tan(radian)
  35.  
  36. #define loop(i,n) for (lli i = 0; i < n; i++)
  37. #define loopitr(xt,vec) for (auto xt : vec)
  38. #define FOR(i,a,b) for (lli i = a; i < b; i+=1)
  39. #define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
  40. #define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
  41. #define itr :: iterator it
  42. #define WL(t) while(t --)
  43.  
  44. #define all(v) v.begin(),v.end()
  45. #define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
  46. #define sz(x) int(x.size())
  47. #define F first
  48. #define S second
  49.  
  50. #define mii map<lli,lli>
  51. #define vi vector<lli>
  52. #define seti set<lli>
  53. #define pii pair<lli,lli>
  54.  
  55. #define gcd(a,b) __gcd((a),(b))
  56. #define lcm(a,b) (a/gcd(a,b))*b
  57. #define abs(x) ((x < 0)?-(x):x)
  58.  
  59. template <typename T>
  60. void print(T x){cout<<x<<endl;}
  61. template <typename T1, typename T2>
  62. void print2(T1 x,T2 y){cout<<x<<" "<<y<<endl;}
  63. template <typename T1, typename T2,typename T3>
  64. void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<endl;}
  65.  
  66. #define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
  67. #define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.push_back(x);}
  68.  
  69. #define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
  70. #define printvector(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";
  71. #define printset(st) for(auto xt : st) cout<<xt<<" ";    cout<<"\n";
  72.  
  73. #define FD(N) fixed<<setprecision(N)
  74.  
  75. #define endl '\n'
  76.  
  77. #define deb(x) cout<<#x<<" "<<x<<endl;
  78.  
  79. /*
  80. ifstream cinn("i3.txt");
  81. ofstream coutt("o3.txt");
  82. */
  83.  
  84.  
  85. bool isvowel(char v) { return (0x208222>>(v&0x1f))&1; }
  86.  
  87. lli mceil(lli a,lli b){
  88.     if(a%b==0) return(a/b);
  89.     else return(a/b  +1);
  90. }
  91. lli mfloor(lli a,lli b){
  92.     return(a/b);
  93. }
  94.  
  95. ll modmul(ll a, ll b) {
  96.     return ((a%mod) * (b%mod)) % mod;
  97. }
  98.  
  99. ll modadd(ll a , ll b){
  100.     return((a%mod)+(b%mod)+mod)%mod;
  101. }
  102.  
  103. ll modsub(ll a , ll b){
  104.     return((a%mod) - (b%mod) + mod)%mod;
  105. }
  106.  
  107. lli fastexpo(lli a,lli b){
  108.     a = a%mod;
  109.     lli ans=1;
  110.     while(b){
  111.         if(b&1)
  112.             ans=(ans*1ll*a)%mod;
  113.         a=(a*1ll*a)%mod;
  114.         b=b/2;
  115.         }
  116.     return ans;
  117.  }
  118.  
  119.  
  120.  
  121.  /* -----------------------------------------------------HASHING-------------------------------------------------------------------*/
  122. /*
  123. some key points -
  124. 1. Use (long int) to remove TLE or Memory Limit issue
  125. 2. If still Wrong answer then may be collision occur , use p as bigger prime no. p : [31,53,107,209,4793]
  126. 3. use mod either 1e9+7
  127. 4 .If it still shows WA then surely collision occurs use Double Hashing
  128.    Double Hashing -
  129.         Make Prehash Array using two different p and mod so chances of collision is less
  130. 5. use pass by reference always
  131.  
  132.  
  133. */
  134.  
  135.  
  136. #define maxlen 1000005 //maximum length of string
  137.  
  138. lli pow_p1[maxlen];
  139. lli p_inv1[maxlen];
  140. lli pow_p2[maxlen];
  141. lli p_inv2[maxlen];
  142.  
  143.  
  144. void init(lli p1, lli p2)
  145. {
  146.     pow_p1[0] = p_inv1[0] = pow_p2[0] = p_inv2[0] = 1;
  147.     lli pinv1 = fastexpo(p1,mod-2);
  148.     lli pinv2 = fastexpo(p2,mod-2);
  149.     for(lli i=1;i<maxlen;i++)
  150.     {
  151.         pow_p1[i] = modmul(pow_p1[i-1],p1);
  152.         p_inv1[i] = modmul(p_inv1[i-1],pinv1);
  153.         pow_p2[i] = modmul(pow_p2[i-1],p2);
  154.         p_inv2[i] = modmul(p_inv2[i-1],pinv2);
  155.     }
  156.  
  157. }
  158.  
  159. struct Hash{
  160.         // 0 based indexing
  161.         lli prehash1[maxlen];
  162.         lli prehash2[maxlen];
  163.         // hash(s) = sigma(i=0 to n-1) s[i]*p^(i)
  164.         // a->1 , b->2 , c->3 and so on
  165.  
  166.  
  167.         void precomputehash(string &s){ //p can be any prime 19 , 31, 53,107 ...
  168.  
  169.  
  170.           prehash2[0] = prehash1[0] = (s[0])+1;
  171.  
  172.             for (lli i=1;i<s.size();i++) {
  173.                 prehash1[i]= modadd(prehash1[i-1] , modmul((s[i]+1),pow_p1[i]));
  174.                 prehash2[i]= modadd(prehash2[i-1] , modmul((s[i]+1),pow_p2[i]));
  175.             }
  176.         }
  177.  
  178.         // hash[l..r] = ((hash[upto r] - hash[upto (l-1)] ) / P^l) % mod = ((hash[upto r] - hash[upto (l-1)] ) * modinv(P^l) )%mod
  179.         pii gethash(lli l, lli r){
  180.             if(l==0)
  181.                 return(make_pair( (prehash1[r]%mod) , (prehash2[r]%mod) ) );
  182.             else{
  183.                 lli ans1 = modsub(prehash1[r],prehash1[l-1]);
  184.                 ans1 = modmul(ans1, p_inv1[l]);
  185.  
  186.                 lli ans2 = modsub(prehash2[r],prehash2[l-1]);
  187.                 ans2 = modmul(ans2, p_inv2[l]);
  188.  
  189.                 return (make_pair(ans1,ans2));
  190.             }
  191.         }
  192.  
  193.         // hash value of all string means hash[0..(n-1)] // 0 based indexing
  194.         pii totalhash(string &s){
  195.             return(make_pair(prehash1[sz(s)-1]%mod , prehash2[sz(s)-1]%mod));
  196.         }
  197. };
  198.  
  199. /* -----------------------------------------------------HASHING-------------------------------------------------------------------*/
  200.  
  201. struct pair_hash
  202. {
  203. 	template <class T1, class T2>
  204. 	std::size_t operator () (std::pair<T1, T2> const &pair) const
  205. 	{
  206. 		std::size_t h1 = std::hash<T1>()(pair.first);
  207. 		std::size_t h2 = std::hash<T2>()(pair.second);
  208.  
  209. 		return h1 ^ h2;
  210. 	}
  211. };
  212.  
  213. bool check(string &a , string &b , Hash &obja , Hash &objb , lli len)
  214. {
  215.     unordered_set<pii,pair_hash> st;
  216.     for(lli i=0;i<=sz(a)-len;i++)
  217.         st.insert(obja.gethash(i,i+len-1));
  218.  
  219.     for(lli i=0;i<=sz(b)-len;i++)
  220.     {
  221.         if(st.find(objb.gethash(i,i+len-1)) != st.end())
  222.             return true;
  223.     }
  224.     return false;
  225.  
  226. }
  227.  
  228.  
  229. int main(){
  230. fastio
  231. lli t=1;
  232. //cin>>t;
  233. init(53,107);
  234. while(t--) {
  235.     string aa,bb,a,b;
  236.     cin>>aa>>bb;
  237.     if(sz(aa)>sz(bb))
  238.     {
  239.         a=aa;
  240.         b=bb;
  241.     }
  242.     else
  243.     {
  244.         a=bb;
  245.         b=aa;
  246.     }
  247.     Hash obja , objb;
  248.     obja.precomputehash(a);
  249.     objb.precomputehash(b);
  250.  
  251.     lli ans = 0;
  252.     lli l = 0;
  253.     lli r = sz(b);
  254.     while(l<=r)
  255.     {
  256.         lli mid = (l+r)/2;
  257.         if(check(a,b,obja,objb,mid))
  258.         {
  259.             l = mid+1;
  260.             ans = mid;
  261.         }
  262.         else
  263.         {
  264.             r = mid-1;
  265.         }
  266.     }
  267.     print(ans);
  268.  
  269.   }
  270. return 0;
  271. }
Success #stdin #stdout 0.01s 34676KB
comments (?)
stdin
copy 
~~~vv~-~~vv~v-v--~-^-~^~-^^
~^~--v~-
stdout
copy 
4
https://ideone.com/pQPfDq
language:
C++14 (gcc 8.3)
created:
3 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!