fork(4) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. string x,y;
  5. const long long B = 26;
  6. const long long M = 1000000007;
  7. long long pb[100005],ipb;
  8. long long power_mod(long long a,long long n)
  9. {
  10. 	if(n==0)
  11. 		return 1;
  12. 	long long int ans = power_mod(a,n/2);
  13. 	ans = (ans%M * ans%M)%M;
  14. 	if(n%2==1)
  15. 		ans = (ans%M * a%M)%M;
  16. 	return ans;
  17. }
  18. int f(int l)
  19. {
  20.     unordered_map<long long,int> mp;
  21.     long long h=0;
  22.     for(int i=0;i<l;i++)
  23.     {
  24.         h = (h%M + ((long long)(x[i]-'a'+1)%M*pb[i]%M)%M)%M;
  25.     }
  26.     mp[h]=1;
  27.     for(int i=l;i<n;i++)
  28.     {
  29.         h=(h%M+ ((long long)(x[i]-'a'+1)%M*pb[l]%M)%M)%M;
  30.         h=(h%M-(long long)(x[i-l]-'a'+1)%M+M)%M;
  31.         h=(h%M*ipb%M)%M;
  32.         mp[h]=1;
  33.     }
  34.     h=0;
  35.     for(int i=0;i<l;i++)
  36.     {
  37.         h = (h%M + ((long long)(y[i]-'a'+1)%M*pb[i]%M)%M)%M;
  38.     }
  39.     if(mp.find(h)!=mp.end())
  40.         return 0;
  41.     for(int i=l;i<n;i++)
  42.     {
  43.         h=(h%M+ ((long long)(y[i]-'a'+1)%M*pb[l]%M)%M)%M;
  44.         h=(h%M-(long long)(y[i-l]-'a'+1)%M+M)%M;
  45.         h=(h%M*ipb%M)%M;
  46.  
  47.         if(mp.find(h)!=mp.end())
  48.         return i-l+1;
  49.     }
  50.     return -1;
  51. }
  52. int main()
  53. {
  54.     pb[0]=1;
  55.     for(int i=1;i<=100000;i++)
  56.         pb[i] = (pb[i-1]%M * B%M)%M;
  57.     ipb = power_mod(B,M-2);
  58. 	cin>>n>>x>>y;
  59.     int l=1,r=n,m,res=-1,st;
  60.     while(l<=r)
  61.     {
  62.         m = (l+r)/2;
  63.         int rr=f(m);
  64.         if(rr!=-1)
  65.         {
  66.             res=m;
  67.             st=rr;
  68.             l=m+1;
  69.         }
  70.         else
  71.             r=m-1;
  72.     }
  73.     cout<<y.substr(st,res)<<endl;
  74. 	return 0;
  75. }
  76.  
Success #stdin #stdout 0s 4236KB
comments ()
stdin 
2
ab
ax
stdout 
a
https://ideone.com/1Lg7Nn
language:
C++14 (gcc 8.3)
created:
6 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!