fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for1(i,m,n) for(int i=m,n_=(n);i<=n_;i++)
  5. #define for0(i,m,n) for(int i=m;i<n;i++)
  6. #define forr1(i,m,n) for(int i=m;i>=n;i--)
  7. #define forr2(i,m,n) for(int i=m;i>n;i--)
  8. #define mini(a,b) (a)=min((a),(b))
  9. #define maxi(a,b) (a)=max((a),(b))
  10. #define ll long long
  11. #define el '\n'
  12. #define fi first
  13. #define se second
  14. #define ii pair<int,int>
  15. #define vll(i) i.begin(),i.end()
  16. #define pb push_back
  17. #define fr front()
  18.  
  19. #define MASK(i) ((1ll) << (i))
  20. #define BIT(i,n) (((i)>>(n))&1)
  21. const string NAME= "hamming";
  22. const int N=1e6;
  23. const int BASE = 27;
  24. const ll MOD=1e9 + 2277 ;
  25. int pw[N + 3], hash[N + 3], f[N + 3], mol[N + 3];
  26. int POW( int n, int k){
  27.   int s = 1;
  28.   while( k){
  29.     if( k % 2 == 1) s = 1ll* s *n %MOD;
  30.     n = 1ll * n * n % MOD;
  31.     k /= 2;
  32.   }
  33.   return s;
  34. }
  35. int main() {
  36. if (fopen((NAME + ".INP").c_str(), "r")) {
  37. freopen((NAME + ".INP").c_str(), "r", stdin);
  38. freopen((NAME + ".OUT").c_str(), "w", stdout);
  39. }
  40. ios::sync_with_stdio(0);
  41. cin.tie(0);
  42. cout.tie(0);
  43. pw[ 0 ] = 1;
  44.   for1(i,1,N) pw[ i ] = 1ll * pw[ i - 1 ] * BASE % MOD;
  45.   string s, k; cin >> s >> k;
  46.   s = ' ' + s;
  47.   k = ' ' + k;
  48.    int K = 0;
  49.   mol[N] = POW(pw[N], MOD - 2);
  50.   forr1(i, N - 1, 0)  mol[i] = (1ll* mol[i + 1] * BASE) % MOD;
  51.  
  52.   for0(i, 1, k.size())
  53.    K =  (1ll* K + 1ll * (k[i] - 'a') * pw[i]) % MOD;
  54.  
  55.  
  56.   for0(i, 1, s.size())
  57.    f[i] = ( 1ll* f[ i - 1] + 1ll* (s[i] - 'a') * pw[i]) % MOD;
  58.   int ans = 0;
  59.   for0(i, k.size() - 1 , s.size() ){
  60.     if( K == 1ll*((f[i] - f[ i - k.size() + 1] ) % MOD + MOD) * mol[i - k.size() + 1 ] % MOD   ) ans ++;
  61.   }
  62.  cout << ans;
  63.  return 0;
  64. }
Success #stdin #stdout 0.02s 13104KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/HINTtz
sau a trong b
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!