Cod sursa(job #1497200)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 6 octombrie 2015 14:07:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 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=lungime-1; i >= len-1; i--)
 {
    poz = i;
    nr = 0;
    p  = 1;
    for (j= poz; j > poz - 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;
    }
   /// cout << nr << endl;
    /// in nr mi-a ramas numarul ce trebuie bagat in hash
    Adauga(nr);
 }
  cnt = 0;
  /// cout << endl;
    /// aici o sa fac pentru primul word
    nr = 0;
    p  = 1;
    for (j=len-1; j>=0; j--)
    {
      if (word[j] == 'a') a = 0;
      if (word[j] == 'b') a = 1;
      if (word[j] == 'c') a = 2;

      nr = nr + p*a;
      p = p*10;
    }
   /// cout << nr << endl;
    Cauta(nr);
    /// ............................

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

      nr = nr + p*a;
      p = p*10;
    }
   /// cout << nr << endl;
    Cauta(nr);
 }

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