Cod sursa(job #2581543)

Utilizator lucametehauDart Monkey lucametehau Data 15 martie 2020 14:25:56
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <unordered_map>

using namespace std;

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

const int P = 5;
const int MOD = 399999947;

int n, m, H, put, cnt;

string a, s;
unordered_map <int, bool> ap;

int main() {
  cin >> a;
  while(cin >> s) {
    H = 0;
    for(int i = 0; i < s.size(); i++)
      H = (H * P + s[i] - 'a' + 1) % MOD;
    ap[H] = 1;
    m = s.size();
  }
  H = 0; put = 1;
  for(int i = 0; i < m; i++) {
    H = (H * P + a[i] - 'a' + 1) % MOD;
    if(i < m - 1)
      put = put * P % MOD;
  }
  if(ap.find(H) != ap.end())
    cnt++;
  for(int i = m; i < a.size(); i++) {
    H = ((H - put * (a[i - m] - 'a' + 1) % MOD + MOD) * P + (a[i] - 'a' + 1)) % MOD;
    if(ap.find(H) != ap.end())
      cnt++;
  }
  cout << cnt;
  return 0;
}