fork download 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int p = 31; 
  12. const int MOD = 1e9 + 9277; 
  13. const int N = 1e6 + 5; 
  14.  
  15. int n, m;  
  16. string s, t;   
  17.  
  18. int p_pow[N], h[N]; 
  19. int h_t;  
  20.  
  21. void precompute() {
  22. 	p_pow[0] = 1;  
  23. 	for (int i = 1; i <= n; i++) {
  24. 		p_pow[i] = 1ll * p_pow[i - 1] * p % MOD; 
  25. 	}
  26.  
  27. 	h[0] = 0;  
  28. 	for (int i = 1; i <= n; i++) {
  29. 		h[i] = (1ll * h[i - 1] * p + (s[i] - 'a' + 1)) % MOD; 
  30. 	}
  31.  
  32. 	h_t = 0;  
  33. 	for (int i = 1; i <= m; i++) {
  34. 		h_t = (1ll * h_t * p + (t[i] - 'a' + 1)) % MOD; 
  35. 	}
  36. }
  37.  
  38. int getHash(int l, int r) {
  39. 	return (h[r] - 1ll * h[l - 1] * p_pow[r - l + 1] % MOD + MOD) % MOD;
  40. }  
  41.  
  42. int main() {
  43. 	ios::sync_with_stdio(false); 
  44. 	cin.tie(nullptr); 	
  45. 	cin >> s; 
  46. 	cin >> t; 
  47. 	n = s.size(), m = t.size();  
  48. 	s = ' ' + s;  
  49. 	t = ' ' + t;  
  50.  
  51. 	precompute();
  52.  
  53. 	int ans = 0;  
  54. 	for (int i = 1; i + m - 1 <= n; i++) {
  55. 		ans += (getHash(i, i + m - 1) == h_t); 
  56. 	}
  57.  
  58. 	cout << ans << '\n';
  59. }
Success #stdin #stdout 0.01s 5684KB
comments (?)
stdin 
saippuakauppias
pp
stdout 
2
https://ideone.com/ztki97
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!