Advertisement
Saleh127

UVA 902 / Hashing

Jan 23rd, 2022
780
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-23-23.53.13
  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.  
  13. ll mod[2]= {1000007707,1000007909};
  14. ll base[2]= {149,307};
  15. ll hash1[2][1000005];
  16. ll hash2[2][50000];
  17. ll p1[1000005];
  18. ll p2[50000];
  19.  
  20. void pwr()
  21. {
  22.     p1[0]=p2[0]=1;
  23.  
  24.     for(ll i=1; i<=1000005; 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)
  32. {
  33.     ///for string a
  34.  
  35.     hash1[0][0]=hash1[1][0]=0;
  36.  
  37.     for(ll i=1; i<=a.size(); i++)
  38.     {
  39.         hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
  40.         //hash1[1][i]=(hash1[1][i-1]*base[1] + a[i-1])%mod[1];
  41.     }
  42. }
  43.  
  44. ll forwardhash(ll l,ll r)
  45. {
  46.     ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];
  47.  
  48.     if(x<0) x+=mod[0];
  49.  
  50.     return x;
  51. }
  52.  
  53. int main()
  54. {
  55.     ios_base::sync_with_stdio(0);
  56.     cin.tie(0);
  57.     cout.tie(0);
  58.  
  59.     pwr();
  60.  
  61.     string a;
  62.     ll n;
  63.  
  64.     while(cin>>n)
  65.     {
  66.         cin>>a;
  67.  
  68.         ll m=0,i,j,k,l,y,z;
  69.  
  70.         hashing(a);
  71.  
  72.         l=a.size();
  73.  
  74.         unordered_map<ll,ll>x;
  75.  
  76.         y=z=-1;
  77.  
  78.         for(i=1; i<=l-n+1; i++)
  79.         {
  80.             k=forwardhash(i,i+n-1);
  81.  
  82.             x[k]++;
  83.  
  84.             //cout<<x[k]<<nl;
  85.  
  86.             if(x[k]>m)
  87.             {
  88.                 m=x[k];
  89.                 y=i-1;
  90.                 z=i+n-2;
  91.             }
  92.         }
  93.  
  94.         if(y>-1)
  95.         {
  96.             for(i=y; i<=z; i++)
  97.             {
  98.                 cout<<a[i];
  99.             }
  100.         }
  101.         cout<<nl;
  102.     }
  103.  
  104.     get_lost_idiot;
  105. }
  106.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement