fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string x,y;
  5. const long long B = 100000007;
  6. const long long M1 = 1000000007;
  7. const long long M2 = 1000000321;
  8. long long pb1[1000005],pb2[1000005],ipb1,ipb2;
  9. long long power_mod(long long a,long long n,const long long M)
  10. {
  11. 	if(n==0)
  12. 		return 1;
  13. 	long long int ans = power_mod(a,n/2,M);
  14. 	ans = (ans%M * ans%M)%M;
  15. 	if(n%2==1)
  16. 		ans = (ans%M * a%M)%M;
  17. 	return ans;
  18. }
  19. int f(int l)
  20. {
  21.     map<long long,int> mp1,mp2;
  22.     long long h1=0,h2=0;
  23.     for(int i=0;i<l;i++)
  24.     {
  25.         h1 = (h1%M1 + ((long long)(x[i])%M1*pb1[i]%M1)%M1)%M1;
  26.         h2 = (h2%M2 + ((long long)(x[i])%M2*pb2[i]%M2)%M2)%M2;
  27.     }
  28.     mp1[h1]=1;
  29.     mp2[h2]=1;
  30.     for(int i=l;i<x.size();i++)
  31.     {
  32.         h1=(h1%M1+ ((long long)(x[i])%M1*pb1[l]%M1)%M1)%M1;
  33.         h1=(h1%M1-(long long)(x[i-l])%M1+M1)%M1;
  34.         h1=(h1%M1*ipb1%M1)%M1;
  35.         mp1[h1]=1;
  36.  
  37.         h2=(h2%M2+ ((long long)(x[i])%M2*pb2[l]%M2)%M2)%M2;
  38.         h2=(h2%M2-(long long)(x[i-l])%M2+M2)%M2;
  39.         h2=(h2%M2*ipb2%M2)%M2;
  40.         mp2[h2]=1;
  41.     }
  42.     h1=0,h2=0;
  43.     for(int i=0;i<l;i++)
  44.     {
  45.         h1 = (h1%M1 + ((long long)(y[i])%M1*pb1[i]%M1)%M1)%M1;
  46.         h2 = (h2%M2 + ((long long)(y[i])%M2*pb2[i]%M2)%M2)%M2;
  47.     }
  48.     if(mp1.find(h1)!=mp1.end() && mp2.find(h2) != mp2.end() )
  49.         return 0;
  50.     for(int i=l;i<y.size();i++)
  51.     {
  52.         h1=(h1%M1+ ((long long)(y[i])%M1*pb1[l]%M1)%M1)%M1;
  53.         h1=(h1%M1-(long long)(y[i-l])%M1+M1)%M1;
  54.         h1=(h1%M1*ipb1%M1)%M1;
  55.  
  56.         h2=(h2%M2+ ((long long)(y[i])%M2*pb2[l]%M2)%M2)%M2;
  57.         h2=(h2%M2-(long long)(y[i-l])%M2+M2)%M2;
  58.         h2=(h2%M2*ipb2%M2)%M2;
  59.         if(mp1.find(h1)!=mp1.end() && mp2.find(h2)!=mp2.end() )
  60.             return i-l+1;
  61.     }
  62.     return -1;
  63. }
  64. int main()
  65. {
  66.     pb1[0]=1LL;
  67.     pb2[0]=1LL;
  68.     for(int i=1;i<=1000000;i++)
  69.     {
  70.         pb1[i] = (pb1[i-1]%M1 * B%M1)%M1;
  71.         pb2[i] = (pb2[i-1]%M2 * B%M2)%M2;
  72.     }
  73.  
  74.     ipb1 = power_mod(B,M1-2,M1);
  75.     ipb2 = power_mod(B,M2-2,M2);
  76. 	cin>>x>>y;
  77.     n = min(x.size(),y.size());
  78.     int l=1,r=n,m,res=-1,st;
  79.     while(l<=r)
  80.     {
  81.         m = (l+r)/2;
  82.         int rr=f(m);
  83.         if(rr!=-1)
  84.         {
  85.             res=m;
  86.             l=m+1;
  87.         }
  88.         else
  89.             r=m-1;
  90.     }
  91.     cout<<res<<endl;
  92. 	return 0;
  93. }
  94.  
Success #stdin #stdout 0.02s 18840KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Fi3nUt
problem ADAPHOTO, based on SPOJ submission 21962199 (CPP14-CLANG), 2018-07-09 06:04:04
language:
C++14 (clang 8.0)
created:
5 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!