Cod sursa(job #2783802)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 15 octombrie 2021 09:08:28
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 1e7;
const int MAXL = 20;
const int mod = 12289;
const int MASK = (1 << 25) - 1;
char s[1 + MAXN], t[1 + MAXL];
vector<unsigned> hash_table[mod];
bitset<1 + MASK> filter;

void Insert(unsigned x) {
  filter[x & MASK] = true;
  int key = x % mod;
  for (auto it : hash_table[key]) {
    if (it == x) {
      return;
    }
  }
  hash_table[key].emplace_back(x);
}

bool check(unsigned x) {
  if (filter[x & MASK] == false) {
    return false;
  }
  int key = x % mod;
  for (auto it : hash_table[key]) {
    if (it == x) {
      return true;
    }
  }
  return false;
}

void test_case() {
  fin >> s;
  int m = 0;
  while (fin >> t) {
    m = strlen(t);
    unsigned val = 0;
    for (int i = 0; i < m; ++i) {
      val = val * 3 + (t[i] - 'a');
    }
    Insert(val);
  }
  unsigned val = 0, pw = 1;
  for (int i = 0; i < m; ++i) {
    val = val * 3 + (s[i] - 'a');
    pw *= 3;
  }
  pw /= 3;
  int n = strlen(s), ans = check(val);
  for (int i = m; i < n; ++i) {
    val -= pw * (s[i - m] - 'a');
    val = val * 3 + (s[i] - 'a');
    ans += check(val);
  }
  fout << ans << '\n';
}

int main() {
  int t = 1;
  for (int tc = 1; tc <= t; ++tc) {
    test_case();
  }
  fin.close();
  fout.close();
  return 0;
}