Cod sursa(job #2802297)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 17 noiembrie 2021 21:22:37
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

const int MOD = 90907;
const int maxN = (int)1e7 + 1;

vector<unsigned int> h[MOD];

char s[maxN], c[21];

int main() {
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  ios_base::sync_with_stdio(false);
  scanf("%s", s);
  unsigned int l = 0, i;
  while (!feof(stdin)) {
    scanf("%s", c);
    unsigned int x = 0;
    for (i = 0; c[i]; i++) {
      x = x * 3 + c[i] - 'a';
    }
    if (find(h[x % MOD].begin(), h[x % MOD].end(), x) != h[x % MOD].end())
      continue;
    h[x % MOD].push_back(x);
  }
  l = strlen(c);
  unsigned int p = 1, x = 0;
  for (i = 0; i < l; i++) {
    x = x * 3 + s[i] - 'a';
    if (i > 0)
      p *= 3;
  }
  unsigned int ans = 0, j, z;
  bool found = false;
  unsigned int xh = x % MOD;
  z = (int)h[xh].size();
  for (j = 0; j < z; j++)
    if (h[xh][j] == x) {
      found = true;
      break;
    }
  if (found)
    ans++;
  for (i = l; s[i]; i++) {
    x = (x - p * (s[i - l] - 'a')) * 3 + s[i] - 'a';
    found = false;
    xh = x % MOD;
    z = (int)h[xh].size();
    for (j = 0; j < z; j++)
      if (h[xh][j] == x) {
        found = true;
        break;
      }
    if (found)
      ans++;
  }
  printf("%d\n", ans);
  return 0;
}