Advertisement
Saleh127

UVA 12494 / Hashing

Jan 4th, 2022
1,161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-04-13.22.40
  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]= {150,300};
  14.  
  15. pair<ll,ll>hashing(string c)
  16. {
  17.     ll n1=0,n2=0;
  18.     ll p1=1,p2=1;
  19.  
  20.     for(ll i=0; c[i]; i++)
  21.     {
  22.         n1=(n1+ (c[i]-'0'+1)*p1)%mod[0];
  23.         n2=(n2+ (c[i]-'0'+1)*p2)%mod[1];
  24.  
  25.         p1=(p1*base[0])%mod[0];
  26.         p2=(p2*base[1])%mod[1];
  27.     }
  28.  
  29.     return {n1,n2};
  30. }
  31.  
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(0);
  35.     cin.tie(0);
  36.     cout.tie(0);
  37.  
  38.  
  39.     test
  40.     {
  41.         string a,b,c;
  42.  
  43.         cin>>a;
  44.  
  45.         set<pair<ll,ll>>x;
  46.  
  47.         ll i,j,k,l;
  48.  
  49.         for(i=1; i<=a.size(); i++)
  50.         {
  51.             for(j=0; j<a.size(); j++)
  52.             {
  53.                 if(i+j>a.size()) break;
  54.  
  55.                 b="";
  56.                 for(k=j; k<(i+j); k++)
  57.                 {
  58.                     b+=a[k];
  59.                 }
  60.  
  61.                 c="";
  62.  
  63.                 for(k=0; k<i; k++)
  64.                 {
  65.                     b=b.back()+b;
  66.                     b.pop_back();
  67.                     c=max(c,b);
  68.                 }
  69.  
  70.                 pair<ll,ll> m=hashing(c);
  71.  
  72.                 x.insert(m);
  73.             }
  74.         }
  75.  
  76.         cout<<x.size()<<nl;
  77.     }
  78.  
  79.     get_lost_idiot;
  80. }
  81.  
  82.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement