Cod sursa(job #2298066)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 7 decembrie 2018 09:29:34
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb

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

const int MAX_LENGTH = 10000000;
const int MOD = 10747333;

char s[MAX_LENGTH + 1];
char word[MAX_LENGTH + 1];
bool 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');
    foundHash[hash % MOD] = true;
  }
  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 = foundHash[hash % MOD];
  for (int i = lWord; i < n; i++) {
    hash -= pow * (s[i - lWord] - 'a');
    hash = hash * 3 + (s[i] - 'a');
    ans += foundHash[hash % MOD];
  }
  printf("%d\n", ans);
  return 0;
}