Cod sursa(job #2581569)

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

using namespace std;

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

const int P = 3;
const int MOD = (int)1e9 + 7;
const int MODH = 666013;

int n, m, cnt;
unsigned H, put;

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

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

void add(unsigned 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 += MOD - put * (a[i - m] - 'a') % MOD;
    if(H > MOD)
      H -= MOD;
    H = (H * P + a[i] - 'a') % MOD;
    if(find(H))
      cnt++;
  }
  cout << cnt;
  return 0;
}