Cod sursa(job #2802233)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 17 noiembrie 2021 20:26:32
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

ifstream in("abc2.in");
ofstream out("abc2.out");

using ll = long long;

const int MOD = 666013;

struct Hash {
  vector<vector<int>> h;
  Hash() : h(MOD, vector<int>{}) {}
  void insert(string &s) {
    int x = 0, p = 1, sum = 0;
    for (int i = 0; i < (int)s.size(); i++) {
      x = (ll)(x * 37 + s[i]) % MOD;
      if (i > 0 && i != (int)s.size() - 1)
        p = (ll)(p * 37) % MOD;
      sum += s[i];
    }
//    cerr << "{" << x << ", " << sum << "}\n";
    h[x].push_back(sum);
  }
  bool find(int x, int s) {
    for (int val : h[x])
      if (val == s)
        return true;
    return false;
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  in.tie(NULL);
  out.tie(NULL);
  string s; in >> s;
  vector<int> v;
  Hash H;
  int l = 0;
  string c; while (in >> c) {
    H.insert(c);
    l = (int)c.size();
  }
  int sum = 0, p = 1, x = 0;
  for (int i = 0; i < l; i++) {
    x = (ll)(x * 37 + s[i]) % MOD;
    if (i > 0) {
      p = (ll)(p * 37) % MOD;
    }
    sum += s[i];
  }
//  cerr << "\n\n";
//  cerr << "{" << x << ", " << sum << "}\n";
  int ans = 0;
  if (H.find(x, sum))
    ans++;
  for (int i = l; i < (int)s.size(); i++) {
    sum += -s[i - l] + s[i];
    x = ((((ll)x - (p * s[i - l] % MOD) + MOD)) % MOD * 37 + s[i]) % MOD;
    if (H.find(x, sum))
      ans++;
//    cerr << "{" << x << ", " << sum << "}\n";
  }
  out << ans << "\n";
  return 0;
}