Saleh127

Light OJ 1347 / Hashing

Jan 6th, 2022 (edited)
219
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-06-22.12.24
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define ull long long
  9. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  10. #define get_lost_idiot return 0
  11. #define nl '\n'
  12. ll mod[2]= {1000007707,1000007909};
  13. ll base[2]= {149,307};
  14. ll hash1[3][1000005];
  15. ll p1[1000005];
  16.  
  17. void pwr()
  18. {
  19.     p1[0]=1;
  20.  
  21.     for(ll i=1; i<=6002; i++)
  22.     {
  23.         p1[i]=(p1[i-1]*base[0])%mod[0];
  24.     }
  25. }
  26.  
  27. void hashing(string a,string b,string c)
  28. {
  29.     hash1[0][0]=hash1[1][0]=hash1[2][0]=0;
  30.  
  31.     for(ll i=1; i<=a.size(); i++)
  32.     {
  33.         hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
  34.     }
  35.     for(ll i=1; i<=b.size(); i++)
  36.     {
  37.         hash1[1][i]=(hash1[1][i-1]*base[0] + b[i-1])%mod[0];
  38.     }
  39.     for(ll i=1; i<=c.size(); i++)
  40.     {
  41.         hash1[2][i]=(hash1[2][i-1]*base[0] + c[i-1])%mod[0];
  42.     }
  43. }
  44.  
  45.  
  46. ll forwardhash1(ll l,ll r)
  47. {
  48.     ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  49.  
  50.     if(x<0) x+=mod[0];
  51.  
  52.     return x;
  53. }
  54.  
  55. ll forwardhash2(ll l,ll r)
  56. {
  57.     ll x=(hash1[1][r] - hash1[1][l-1]*p1[r-l+1])%mod[0];
  58.  
  59.     if(x<0) x+=mod[0];
  60.  
  61.     return x;
  62. }
  63.  
  64. ll forwardhash3(ll l,ll r)
  65. {
  66.     ll x=(hash1[2][r] - hash1[2][l-1]*p1[r-l+1])%mod[0];
  67.  
  68.     if(x<0) x+=mod[0];
  69.  
  70.     return x;
  71. }
  72.  
  73. unordered_map<ll,ll>x;
  74.  
  75. int main()
  76. {
  77.     ios_base::sync_with_stdio(0);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80.  
  81.     pwr();
  82.  
  83.  
  84.     test
  85.     {
  86.  
  87.         string a,b,c;
  88.  
  89.         ll n,i,j,k,l,h,ans=0;
  90.  
  91.  
  92.         cin>>a;
  93.         cin>>b;
  94.         cin>>c;
  95.  
  96.         hashing(a,b,c);
  97.  
  98.         ll s1,s2,s3;
  99.  
  100.         s1=a.size();
  101.         s2=b.size();
  102.         s3=c.size();
  103.  
  104.         l=1ll,h=min({s1,s2,s3});
  105.  
  106.         while(l<=h)
  107.         {
  108.             ll m=0;
  109.  
  110.             ll mid=(l+h)/2;
  111.  
  112.             x.clear();
  113.  
  114.             for(i=1; i<=(s1-mid+1); i++)
  115.             {
  116.                 ll h1=forwardhash1(i,i+mid-1);
  117.  
  118.                 x[h1]=1;
  119.             }
  120.  
  121.             for(j=1; j<=(s2-mid+1); j++)
  122.             {
  123.                 ll h2=forwardhash2(j,j+mid-1);
  124.  
  125.                 if(x.count(h2))
  126.                 {
  127.                     x[h2]=2;
  128.                 }
  129.             }
  130.  
  131.             for(k=1; k<=(s3-mid+1); k++)
  132.             {
  133.                 ll h3=forwardhash3(k,k+mid-1);
  134.  
  135.                 if(x[h3]==2)
  136.                 {
  137.                     m=1;
  138.                     break;
  139.                 }
  140.             }
  141.  
  142.             if(m==1)
  143.             {
  144.                 ans=mid;
  145.                 l=mid+1;
  146.             }
  147.             else
  148.             {
  149.                 h=mid-1;
  150.             }
  151.  
  152.         }
  153.  
  154.         cout<<"Case "<<cs<<": "<<ans<<nl;
  155.  
  156.     }
  157.  
  158.     get_lost_idiot;
  159. }
  160.  
  161.  
RAW Paste Data Copied