Advertisement
Saleh127

UVA 12206 / Hashing

Jan 5th, 2022
608
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-05-19.51.04
  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][50000];
  15. ll hash2[2][50000];
  16. ll p1[50000];
  17. ll p2[50000];
  18.  
  19. void pwr()
  20. {
  21.     p1[0]=p2[0]=1;
  22.  
  23.     for(ll i=1; i<=50000; 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. unordered_map<ll,ll>x;
  53.  
  54. int main()
  55. {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);
  58.     cout.tie(0);
  59.  
  60.     pwr();
  61.  
  62.     ll m;
  63.  
  64.     while(cin>>m)
  65.     {
  66.  
  67.         if(m==0) break;
  68.  
  69.         string a;
  70.  
  71.         cin>>a;
  72.  
  73.         hashing(a);
  74.  
  75.         ll n,i,j,k,l,h,ans=0,in;
  76.  
  77.         n=a.size();
  78.  
  79.         l=1,h=n;
  80.  
  81.         while(l<=h)
  82.         {
  83.             ll mid=(l+h)/2;
  84.  
  85.             j=0;
  86.  
  87.             x.clear();
  88.  
  89.             for(i=1;i<=n-mid+1;i++)
  90.             {
  91.  
  92.                 k=forwardhash(i,i+mid-1);
  93.  
  94.                 x[k]+=1;
  95.  
  96.                 if(x[k]>=m)
  97.                 {
  98.                      j=1;
  99.                      ans=mid;
  100.                      in=i;
  101.                 }
  102.  
  103.             }
  104.  
  105.             if(j==1) l=mid+1;
  106.             else h=mid-1;
  107.  
  108.         }
  109.  
  110.          if(ans==0) cout<<"none"<<nl;
  111.          else cout<<ans<<" "<<in-1<<nl;
  112.     }
  113.  
  114.     get_lost_idiot;
  115. }
  116.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement