Cod sursa(job #2297721)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 6 decembrie 2018 13:01:32
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <cstring>
#include <cctype>
#include <unordered_map>

const int MAX_LENGTH = 10000000;
const int MOD = 1544407;

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