Cod sursa(job #2802250)

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

using namespace std;

#define int unsigned int

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

const int MOD = 90911;

vector<int> h[MOD];

void insert(string &s) {
  int x = 0;
  for (int i = 0; i < (int)s.size(); i++) {
    x = x * 3 + s[i] - 'a';
  }
  h[x % MOD].push_back(x);
}

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

signed main() {
  ios_base::sync_with_stdio(false);
  in.tie(NULL);
  string s; in >> s;
  vector<int> v;
  int l = 0;
  string c; while (in >> c) {
    insert(c);
    l = (int)c.size();
  }
  int p = 1, x = 0;
  for (int i = 0; i < l; i++) {
    x = x * 3 + s[i] - 'a';
    if (i > 0)
      p *= 3;
  }
  int ans = 0;
  if (find(x))
    ans++;
  for (int i = l; i < (int)s.size(); i++) {
    x = (x - p * (s[i - l] - 'a')) * 3 + s[i] - 'a';
    if (find(x))
      ans++;
  }
  out << ans << "\n";
  return 0;
}