Cod sursa(job #2802312)

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

using namespace std;

const unsigned int MOD = 90911;
const unsigned int maxN = (int)1e7 + 1;

vector<unsigned int> h[MOD];

char s[maxN], c[21];

bool find(unsigned int x) {
  unsigned int n = h[x % MOD].size();
  for (unsigned int i = 0; i < n; i++)
    if (h[x % MOD][i] == x)
      return true;
  return false;
}

void add(unsigned int x) {
  if (!find(x))
    h[x % MOD].push_back(x);
}

int main() {
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  scanf("%s", s);
  unsigned int i = 0, h = 0, l = 0;
  while (!feof(stdin)) {
    scanf("%s", c);
    l = strlen(c);
    h = 0;
    for (i = 0; i < l; i++)
      h = h * 3 + c[i] - 'a';
    add(h);
  }
  unsigned int ans = 0, p = 1, ll = strlen(s);
  h = 0;
  for (i = 0; i < l; i++) {
    h = h * 3 + s[i] - 'a';
    p *= 3;
  }
  p /= 3;
  ans += find(h);
  for (i = l; i < ll; i++) {
    h = (h - p * (s[i - l] - 'a')) * 3 + s[i] - 'a';
    if (find(h))
      ans++;
  }
  printf("%d\n", ans);
  return 0;
}