fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
  3. #define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
  4. #define pub push_back
  5. #define pii pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define int long long
  9. using namespace std;
  10.  
  11. const int N = 1e6 + 10;
  12. const int M = 350;
  13. const int mod = 2e9 + 11;
  14. const int LOG = 19;
  15. const long long inf = 3e18;
  16.  
  17. string s, t;
  18. int n, m, k, ans = 0;
  19. int prefix[N];
  20. int base[N], f1[N], f2[N];
  21. int hash_t;
  22.  
  23. int minusMod(int a, int b) {
  24.     return ((a % mod) - (b % mod) + mod) % mod;
  25. }
  26. int mulMod(int a, int b) {
  27.     return ((a % mod) * (b % mod)) % mod;
  28. }
  29. void calBase() {
  30.     base[0] = 1;
  31.     FOR(i, 1, n, 1) {
  32.         base[i] = (base[i - 1] * 256) % mod;
  33.     }
  34. }
  35. void hashing(string &s, int *f) {
  36.     FOR(i, 1, n, 1) {
  37.         f[i] = (f[i - 1] * 256 + s[i]) % mod;
  38.     }
  39. }
  40. int getHash(int l, int r, int *f) {
  41.     int x = minusMod(f[r], mulMod(f[l - 1], base[r - l + 1]));
  42.     return x;
  43. }
  44. void input() {
  45.     getline(cin, s);
  46.     getline(cin, t);
  47.     cin >> k;
  48.     n = s.size(), m = t.size();
  49.     s = ' ' + s;
  50.     t = ' ' + t;
  51.     calBase();
  52.     hashing(s, f1);
  53.     hashing(t, f2);
  54.     hash_t = getHash(1, m, f2);
  55. }
  56. void solve() {
  57.     input();
  58.     FOR(i, 1, n - m + 1, 1) {
  59.         int l = i;
  60.         int r = i + m - 1;
  61.         if (getHash(l, r, f1) == hash_t) {
  62.             prefix[i] ++;
  63.         }
  64.     }
  65.     FOR(i, 1, n, 1){
  66.         prefix[i] = prefix[i - 1] + prefix[i];
  67.     }
  68.     FOR(i, 1, n - k + 1, 1) {
  69.         int l = i;
  70.         int r = i + k - 1;
  71.         if (prefix[r - m + 1] - prefix[l - 1] > 0) {
  72.             ++ans;
  73.         }
  74.     }
  75.     cout << ans << '\n';
  76. }
  77. signed main() {
  78.     #define name "baitap"
  79.     if (ifstream(name".inp")) {
  80.         freopen(name".inp", "r", stdin);
  81.         freopen(name".out", "w", stdout);
  82.     }
  83.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  84.     solve();
  85. }
  86.  
Success #stdin #stdout 0.01s 7668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/GVkHvY
language:
C++ (gcc 8.3)
created:
2 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!