Cod sursa(job #2783793)

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

using namespace std;

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

const int mod = 1572869;
vector<int> hash_table[mod];

void Insert(int64_t x) {
  int key = x % mod;
  for (int it : hash_table[key]) {
    if (it == x) {
      return;
    }
  }
  hash_table[key].emplace_back(x);
}

bool check(int64_t x) {
  int key = x % mod;
  for (int it : hash_table[key]) {
    if (it == x) {
      return true;
    }
  }
  return false;
}

void test_case() {
  string s, t;
  fin >> s;
  int m;
  while (fin >> t) {
    m = t.size();
    int64_t val = 0;
    for (char c : t) {
      val = val * 3 + (c - 'a');
    }
    Insert(val);
  }
  int64_t val = 0, pw = 1;
  for (int i = 0; i < m; ++i) {
    val = val * 3 + (s[i] - 'a');
    pw *= 3;
  }
  pw /= 3;
  int n = s.size();
  int 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;
}