fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e6;
  5.  
  6. int n, m;
  7. string s, t;
  8.  
  9. long long base = 31;
  10. long long hs[MAXN + 5], pwr[MAXN + 5];
  11.  
  12. long long get(int l, int r)
  13. {
  14.     return hs[r] - hs[l - 1] * pwr[r - l + 1];
  15. }
  16.  
  17. void solve()
  18. {
  19.     cin >> s >> t;
  20.     n = s.size();
  21.     m = t.size();
  22.     s = ' ' + s;
  23.     t = ' ' + t;
  24.  
  25.     long long hs_s = 0;
  26.     for (int i = 1; i <= n; i++) {
  27.         hs_s = hs_s * base + s[i] - 'A' + 1;
  28.     }
  29.  
  30.     pwr[0] = 1;
  31.     for (int i = 1; i <= m; i++) {
  32.         hs[i] = hs[i - 1] * base + t[i] - 'A' + 1;
  33.  
  34.         // không thực sự cần thiết cho bài này bởi mỗi xâu truy vấn đều cùng độ dài
  35.         pwr[i] = pwr[i - 1] * base;
  36.     }
  37.  
  38.     int res = 0;
  39.     for (int i = 1; i + n - 1 <= m; i++) {
  40.         if (get(i, i + n - 1) == hs_s) {
  41.             res++;
  42.         }
  43.     }
  44.  
  45.     cout << res << '\n';
  46. }
  47.  
  48. int main()
  49. {
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.  
  53.     solve();
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/TpnLQz
language:
C++14 (gcc 8.3)
created:
13 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!