Cod sursa(job #1061074)

Utilizator cahemanCasian Patrascanu caheman Data 19 decembrie 2013 10:16:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>

using namespace std;

string text, cuv;

vector <unsigned int> hh[66013];

unsigned int p;

void hashuire(unsigned int x)
{
  int m;
  m = x % 66013;
  for(vector <unsigned int> :: iterator it = hh[m].begin(); it != hh[m].end(); ++ it)
    if((*it) == x)
      return ;
  hh[m].push_back(x);
}

bool verif(unsigned int x)
{
  int m;
  m = x % 66013;
  for(vector <unsigned int> :: iterator it = hh[m].begin(); it != hh[m].end(); ++ it)
    if((*it) == x)
      return 1;
  return 0;
}

int main()
{
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  unsigned int x;
  int n, m, i, j, nr = 0;
  cin>>text;
  n = text.length();
  while(! cin.eof())
  {
    x = 0;
    cin>>cuv;
    m = cuv.length();
    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 < n; ++ i)
  {
    x = (x * 3 + text[i] - 'a') % p;
    if(verif(x))
      ++ nr;
  }
  printf("%d\n", nr);
  return 0;
}