Cod sursa(job #2297674)

Utilizator cahemanCasian Patrascanu caheman Data 6 decembrie 2018 10:43:12
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<cstdio>
#include<vector>
#include<cstring>
#pragma GCC optimize("03")
using namespace std;

char text[10000005];
char cuv[25];

vector <unsigned int> hh[10041];

inline void hashuire(unsigned int x)
{
  unsigned int m;
  m = x % 10041;
  for(auto it:hh[m])
    if(it == x)
      return ;
  hh[m].push_back(x);
}

inline bool verif(unsigned int x)
{
  unsigned int m;
  m = x % 10041;
  for(auto it:hh[m])
    if(it == x)
      return 1;
  return 0;
}

int main()
{
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  unsigned int x, p;
  int n, i, j, nr = 0, m = 0;
  scanf("%s", &text);
  n = 0;
  n=strlen(text);
  while(scanf("%s", &cuv)!=EOF)
  {
    m = strlen(cuv);
    x = 0;
    for(i = 0; i < m; ++ i)
      x = x * 3 + cuv[i] - 'a';
    hashuire(x);
  }
  x = 0;
  p = 1;
  for(i = 1; i < m; ++ i)
    p = p * 3;
  for(i = 0; i < m - 1; ++ i)
    x = x * 3 + text[i] - 'a';
  for(i = m - 1; i < n; ++ i)
  {
    x = x * 3 + text[i] - 'a';
    nr += verif(x);
    x = x - p * (text[i - m + 1] - 'a');
  }
  printf("%d\n", nr);
  return 0;
}