Cod sursa(job #1497170)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 6 octombrie 2015 12:28:38
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb

#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#define Nmax 10000006
#define P 123457

using namespace std;

ifstream fin ("abc2.in");
ofstream fout ("abc2.out");

struct Hashing{
  long long int x;  /// x-ul retine valoarea cuvantului in baza 3
  int  y; /// y-ul retine valorea numarul de aparitii ale cuvantului resp. in s[]
};

vector <Hashing> L[P+3];

char word[25], s[Nmax]; /// sirul de cuvinte retinut
int len, lungime, cnt;

void Adauga(long long int x)
{
  int r,j;
  r = x % P;

  for (j=0; j<L[r].size(); j++)
  {
      if (L[r][j].x == x)
      {
          L[r][j].y++;
          return;
      }
  }
  Hashing q;
  q.x = x;
  q.y = 1;
  L[r].push_back(q);
}

void Cauta(long long int x)
{
  int r,j;
  r = x % P;

  for (j=0; j<L[r].size(); j++)
  {
      if (L[r][j].x == x)
      {
          cnt = cnt + L[r][j].y;
          L[r][j].x = L[r][L[r].size()-1].x;
          L[r][j].y = L[r][L[r].size()-1].y;
          L[r].pop_back();
          return;
      }
  }
}

int main ()
{
 long long int nr;
 long long int p;
 int i,poz, j, a;

 fin >> s;
 lungime = strlen(s);
 fin >> word;
 len = strlen(word);

 /// converteste sirul in baza 3

 for (i=0; i<lungime; i++)
 {
    poz = i;
    nr = 0;
    p  = 1;
    for (j= poz; j < poz + len && s[j]!=0; j++)
    {
        if (s[j] == 'a') a = 0;
        if (s[j] == 'b') a = 1;
        if (s[j] == 'c') a = 2;

        nr = nr + p*a;
        p = p*10;
    }
    /// in nr mi-a ramas numarul ce trebuie bagat in hash
    Adauga(nr);
 }

 cnt = 0;

 while (fin>>word)
 {
    nr = 0;
    p  = 1;
    for (j=0; j<len; j++)
    {
      if (s[j] == 'a') a = 0;
      if (s[j] == 'b') a = 1;
      if (s[j] == 'c') a = 2;

      nr = nr + p*a;
      p = p*10;
    }
    Cauta(nr);
 }

 fout << cnt;
 fin.close();
 fout.close();
 return 0;
}