Advertisement
Saleh127

Light OJ 1255 / Hashing - Substring find

Jan 1st, 2022
1,226
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2022-01-02-01.09.39
  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. ll hash1[1000007];
  15. ll hash2[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.      hash1[0]=hash2[0]=0;
  33.  
  34.      for(ll i=1;i<=a.size();i++)
  35.      {
  36.           hash1[i]=(hash1[i-1]*base[0] + a[i-1])%mod[0];
  37.           hash2[i]=(hash2[i-1]*base[1] + a[i-1])%mod[1];
  38.      }
  39. }
  40.  
  41. ll rangehash1(ll l,ll r)
  42. {
  43.      if(l==1) return hash1[r];
  44.  
  45.      ll x=(hash1[r] - hash1[l-1]*p1[r-l+1])%mod[0];
  46.  
  47.      x+=mod[0];
  48.  
  49.      return x%mod[0];
  50. }
  51.  
  52. ll rangehash2(ll l,ll r)
  53. {
  54.      if(l==1) return hash2[r];
  55.  
  56.      ll x=(hash2[r] - hash2[l-1]*p2[r-l+1])%mod[1];
  57.  
  58.      x+=mod[1];
  59.  
  60.      return x%mod[1];
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66.    ios_base::sync_with_stdio(0);
  67.    cin.tie(0);cout.tie(0);
  68.  
  69.    ll n,m,i,j,k,l;
  70.  
  71.    pwr();
  72.  
  73.  
  74.    test
  75.    {
  76.         string a,b;
  77.  
  78.         cin>>b;
  79.         cin>>a;
  80.  
  81.         l=a.size();
  82.  
  83.         hashing(a);
  84.  
  85.         ll hv1=rangehash1(1,l);
  86.         ll hv2=rangehash2(1,l);
  87.  
  88.         hashing(b);
  89.  
  90.         m=0;
  91.  
  92.         for(i=1;i+l-1<=b.size();i++)
  93.         {
  94.              ll v1=rangehash1(i,i+l-1);
  95.              ll v2=rangehash2(i,i+l-1);
  96.  
  97.              if(v1==hv1 && hv2==v2)
  98.              {
  99.                   m++;
  100.              }
  101.         }
  102.  
  103.         cout<<"Case "<<cs<<": "<<m<<nl;
  104.    }
  105.  
  106.    get_lost_idiot;
  107. }
  108.  
  109.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement