Advertisement
Saleh127

UVA 11512 / Hashing

Jan 5th, 2022
439
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=0,i,j,k,l,h,yy=0;
  64.  
  65.         string a,b="";
  66.  
  67.         cin>>a;
  68.  
  69.         hashing(a);
  70.  
  71.         k=1;
  72.  
  73.         n=a.size();
  74.  
  75.         map<ll,ll>x;
  76.  
  77.         l=1,h=n;
  78.  
  79.         while(l<=h)
  80.         {
  81.             ll mid=(l+h)/2;
  82.  
  83.  
  84.             yy=0;
  85.  
  86.             for(i=1;i<=n-mid+1;i++)
  87.             {
  88.                  k=forwardhash(i,i+mid-1);
  89.  
  90.                  x[k]++;
  91.  
  92.                  if(x[k]>=2)
  93.                  {
  94.  
  95.                       yy=1;
  96.  
  97.                       string d=a.substr(i-1,mid);
  98.  
  99.                       if(mid==b.size())
  100.                       {
  101.                            if(min(b,d)==d)
  102.                            {
  103.                                 m=x[k];
  104.                                 b=d;
  105.                            }
  106.                       }
  107.                       else if(mid>b.size())
  108.                       {
  109.                            m=x[k];
  110.                            b=d;
  111.                       }
  112.                  }
  113.             }
  114.  
  115.             if(yy) l=mid+1;
  116.             else h=mid-1;
  117.  
  118.         }
  119.  
  120.         if(m==0) cout<<"No repetitions found!"<<nl;
  121.         else cout<<b<<" "<<m<<nl;
  122.  
  123.     }
  124.  
  125.     get_lost_idiot;
  126. }
  127.  
  128.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement