Cod sursa(job #2581631)

Utilizator lucametehauDart Monkey lucametehau Data 15 martie 2020 16:02:58
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int MOD = 666013;

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

char a[10000005], s[25];
vector <unsigned> g[MOD];

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

void add(unsigned nr) {
  g[nr % MOD].emplace_back(nr);
}

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