Cod sursa(job #2297644)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 6 decembrie 2018 10:06:58
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int MOD = 90907;

unordered_map<unsigned int, bool>x;

char s[10000005], c[25];
vector<unsigned int>G[MOD + 5];

bool cauta(unsigned int val) {
  unsigned int v1 = val % MOD;
  for (auto it:G[v1])
    if (it == val)
      return 1;
  return 0;
}

int main() {
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);

  scanf("%s", s);
  int l = -1;
  unsigned int val = 0;
  while(scanf("%s", c) != EOF) {
    if (l == -1)
      l = strlen(c);
    val = 0;
    for (int i = 0; i < l; ++i)
      val = val * 3 + c[i] - 'a';
    G[val % MOD].push_back(val);
  }

  int n = strlen(s), ans = 0;
  val = 0;
  unsigned int p3 = 1;
  for (int j = 0; j < l; ++j)
    val = val * 3 + s[j] - 'a', p3 *= 3;
  p3 /= 3;
  for (int i = 0; i + l - 1 < n; ++i) {
    ans += cauta(val);
    val = val - (s[i] - 'a') * p3;
    val *= 3;
    val += s[i + l] - 'a';
  }

  printf("%d\n", ans);

  return 0;
}