Advertisement
Saleh127

UVA 11475 / Hashing

Jan 2nd, 2022
1,122
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-02-01.09.39
  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][100007];
  15. ll hash2[2][100007];
  16. ll p1[100007];
  17. ll p2[100007];
  18.  
  19.  
  20. void pwr()
  21. {
  22.      p1[0]=p2[0]=1;
  23.  
  24.      for(ll i=1;i<=100005;i++)
  25.      {
  26.           p1[i]=(p1[i-1]*base[0])%mod[0];
  27.           p2[i]=(p2[i-1]*base[1])%mod[1];
  28.      }
  29. }
  30.  
  31. void hashing(string a,string b)
  32. {
  33.  
  34.      ///for string a
  35.  
  36.      hash1[0][0]=hash1[1][0]=0;
  37.  
  38.      for(ll i=1;i<=a.size();i++)
  39.      {
  40.           hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
  41.           hash1[1][i]=(hash1[1][i-1]*base[1] + a[i-1])%mod[1];
  42.      }
  43.  
  44.      ///for string b
  45.  
  46.      hash2[0][0]=hash2[1][0]=0;
  47.  
  48.      for(ll i=1;i<=b.size();i++)
  49.      {
  50.           hash2[0][i]=(hash2[0][i-1]*base[0] + b[i-1])%mod[0];
  51.           hash2[1][i]=(hash2[1][i-1]*base[1] + b[i-1])%mod[1];
  52.      }
  53.  
  54. }
  55.  
  56. pair<ll,ll> rangehash1(ll l,ll r)
  57. {
  58.      if(l==1) return {hash1[0][r],hash1[1][r]};
  59.  
  60.      ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  61.  
  62.      ll y=(hash1[1][r] - hash1[1][l-1]*p2[r-l+1])%mod[1];
  63.  
  64.      if(x<0) x+=mod[0];
  65.  
  66.      if(y<0) y+=mod[1];
  67.  
  68.      return {x,y};
  69. }
  70.  
  71. pair<ll,ll> rangehash2(ll l,ll r)
  72. {
  73.      if(l==1) return {hash2[0][r],hash2[1][r]};
  74.  
  75.      ll x=(hash2[0][r] - hash2[0][l-1]*p1[r-l+1])%mod[0];
  76.  
  77.      ll y=(hash2[1][r] - hash2[1][l-1]*p2[r-l+1])%mod[1];
  78.  
  79.      if(x<0) x+=mod[0];
  80.  
  81.      if(y<0) y+=mod[1];
  82.  
  83.      return {x,y};
  84. }
  85.  
  86.  
  87. int main()
  88. {
  89.    ios_base::sync_with_stdio(0);
  90.    cin.tie(0);cout.tie(0);
  91.  
  92.  
  93.    pwr();
  94.  
  95.    string a,b;
  96.  
  97.    ll n,m,i,j,k,l;
  98.  
  99.    while(cin>>a)
  100.    {
  101.         b=a;
  102.  
  103.         reverse(b.begin(),b.end());
  104.  
  105.         hashing(a,b);
  106.  
  107.         l=k=a.size();
  108.  
  109.         m=l;
  110.  
  111.         for(i=1,j=1; k>=1; k--,j++)
  112.         {
  113.              pair<ll,ll>xx,yy;
  114.  
  115.              xx = rangehash1(k,l);
  116.              yy = rangehash2(i,j);
  117.  
  118.              if(xx.first==yy.first && xx.second==yy.second)
  119.              {
  120.                   m=min(m,k);
  121.              }
  122.         }
  123.  
  124.         string c="";
  125.  
  126.         for(i=0;i<m-1;i++)
  127.         {
  128.              c+=a[i];
  129.         }
  130.  
  131.         reverse(c.begin(),c.end());
  132.  
  133.         cout<<a<<c<<endl;
  134.    }
  135.  
  136.  
  137.    get_lost_idiot;
  138. }
  139.  
  140.  
  141.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement