Advertisement
Saleh127

UVA 12467 / Hashing

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