Cod sursa(job #2298074)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 7 decembrie 2018 09:39:13
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb

#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>

const int MAX_LENGTH = 10000000;
const int MOD = 10041;

char s[MAX_LENGTH + 1];
char word[MAX_LENGTH + 1];
std::vector<unsigned int> foundHash[MOD];

int main() {
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  
  scanf("%s", s);
  int n = (int)strlen(s);
  int lWord = 0;
  while (scanf("%s", word) != EOF) {
    lWord = (int)strlen(word);
    unsigned int hash = 0;
    for (int i = 0; i < lWord; i++)
      hash = hash * 3 + (word[i] - 'a');
    bool ok = true;
    for (auto it : foundHash[hash % MOD]) {
      if (it == hash) {
        ok = false;
        break;
      }
    }
    if (ok)
      foundHash[hash % MOD].push_back(hash);
  }
  unsigned int pow = 1;
  for (int i = 1; i < lWord; i++)
    pow *= 3;
  unsigned int hash = 0;
  for (int i = 0; i < lWord; i++)
    hash = hash * 3 + (s[i] - 'a');
  int ans = 0;
  for (auto it : foundHash[hash % MOD]) {
    if (it == hash) {
      ans++;
      break;
    }
  }
  for (int i = lWord; i < n; i++) {
    hash -= pow * (s[i - lWord] - 'a');
    hash = hash * 3 + (s[i] - 'a');
    for (auto it : foundHash[hash % MOD]) {
      if (it == hash) {
        ans++;
        break;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}