Cod sursa(job #2783799)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 15 octombrie 2021 09:02:28
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 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 << 23) - 1;
char s[1 + MAXN], t[1 + MAXL];
bitset<MASK + 1> filter;

typedef struct element {
  int val;
  element *next;
} *lista;

lista h[mod];

void add(int x) {
  filter[x & MASK] = true;
  int key = x % mod;
  lista p;
  for (p = h[key]; p; p = p->next) {
    if (p->val == x) {
      return;
    }
  }
  p = new element;
  p->val = x;
  p->next = h[key];
  h[key] = p;
}

bool check(int x) {
  if (filter[x & MASK] == false) {
    return 0;
  }
  int key = x % mod;
  for (lista p = h[key]; p; p = p->next) {
    if (p->val == 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');
    }
    add(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;
}