fork(1) download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int base = 37;
  6. const int mod = 1000004329;
  7. const int N = 1e6 + 1;
  8. long long hashh[N], Inverse[N], p[N];
  9. long long target = 0;
  10. long long bin_expo(long long b, long long p)
  11. {
  12.     if (p == 0) return 1;
  13.     if (p % 2 == 0) {
  14.         long long half = bin_expo(b, p / 2);
  15.         return (half * half) % mod; 
  16.     } else {
  17.         return (b * bin_expo(b, p - 1)) % mod;
  18.     }
  19. }
  20.  
  21. void power()
  22. {
  23.     p[0] = 1;
  24.     for (int i = 1; i < N; i++) {
  25.         p[i] = (p[i - 1] * base) % mod;
  26.         Inverse[i] = bin_expo(p[i], mod - 2); 
  27.     }
  28. }
  29. void hashh1(string s)
  30. {
  31.     long long pre = 0;
  32.     int n=s.size();
  33.     for (int i = 0; i < n; i++) {
  34.         pre = pre + ((s[i] - 'a' + 1) * p[i]) % mod;
  35.         pre %= mod;
  36.         hashh[i] = pre;
  37.     }
  38. }
  39. void hashh2(string s)
  40. {
  41.     long long pre = 0;
  42.     int n=s.size();
  43.     for (int i = 0; i < n ;i++) {
  44.         pre = pre + ((s[i] - 'a' + 1) * p[i]) % mod;
  45.         pre %= mod;
  46.     }
  47.     target = pre;
  48. }
  49.  
  50. long long range_hash(int i, int j)
  51. {
  52.     long long res = hashh[j];
  53.     if (i - 1 >= 0) {
  54.         res -= hashh[i - 1];
  55.         res = (res + mod) % mod;
  56.     }
  57.     res = (res*bin_expo(p[i],mod-2))%mod;
  58.     return res; 
  59. }
  60.  
  61. int main()
  62. {
  63.     string n, m;
  64.     cin >> n >> m;
  65.     power();
  66.     hashh1(n);
  67.     hashh2(m);
  68.     int a = n.size(), b = m.size(), ans = 0;
  69.     for (int i = 0; i + b - 1 < a; i++) {
  70.         if (range_hash(i, i + b - 1) == target) ans++;
  71.     }
  72.     cout << ans << "\n";
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.28s 19364KB
comments (?)
stdin
copy 
saippuakauppias
pp
stdout
copy 
2
https://ideone.com/PBE0iS
String hashing
language:
C++14 (gcc 8.3)
created:
17 days 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!