Cod sursa(job #2581562)

Utilizator lucametehauDart Monkey lucametehau Data 15 martie 2020 14:46:55
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int P = 3;
const int MOD = 715827829;
const int MODH = 666013;

int n, m, H, put, cnt;

string a, s;
vector <int> g[MODH];

bool find(int nr) {
  for(auto &i : g[nr % MODH]) {
    if(i == nr)
      return 1;
  }
  return 0;
}

void add(int nr) {
  g[nr % MODH].push_back(nr);
}

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