Saleh127

UVA 1314 / Hashing String Rotation

Jan 5th, 2022 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-04-14.17.10
  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]= {26,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)
  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.  
  43. ll forwardhash(ll l,ll r)
  44. {
  45.     ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  46.  
  47.     if(x<0) x+=mod[0];
  48.  
  49.     return x;
  50. }
  51.  
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.  
  58.     pwr();
  59.  
  60.  
  61.     test
  62.     {
  63.         ll n,m,i,j,k,l,h;
  64.  
  65.         string a;
  66.  
  67.         cin>>n>>a;
  68.  
  69.         a+=a;
  70.  
  71.         hashing(a);
  72.  
  73.         k=1;
  74.  
  75.         for(i=2;i<=n;i++)
  76.         {
  77.              l=0,h=n-1;
  78.  
  79.              while(l<=h)
  80.              {
  81.                   ll mid=(l+h)/2;
  82.  
  83.                   if(forwardhash(k,k+mid)==forwardhash(i,i+mid))
  84.                   {
  85.                        l=mid+1;
  86.                   }
  87.                   else
  88.                   {
  89.                        h=mid-1;
  90.                   }
  91.              }
  92.  
  93.              if(l<=n-1)
  94.              {
  95.                   if(a[i+l-1]<a[k+l-1])
  96.                   {
  97.                        k=i;
  98.                   }
  99.              }
  100.         }
  101.  
  102.         //cout<<a.substr(k-1,n)<<nl;
  103.  
  104.         cout<<k-1<<nl;
  105.  
  106.     }
  107.  
  108.     get_lost_idiot;
  109. }
  110.  
RAW Paste Data Copied