Cod sursa(job #2013072)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 20 august 2017 14:05:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define prim 10007

using namespace std;
ifstream fi ("abc2.in");
ofstream fo ("abc2.out");

string sir,cuvant[50006];
long long i,j,nrcuv,lgcuv,lgsir,sol;
vector <long long> v[10010];

bool caut(long long x,long long cheie)
{
//  for (long long q=0;q<v[cheie].size();q++)
//    if (v[cheie][q]==x) return 1;
  return 0;
}

void citire()
{
  fi>>sir;
  while (fi>>cuvant[nrcuv+1]) nrcuv++;
  lgcuv=cuvant[1].size();
  lgsir=sir.size();
}

void transformare()
{
  long long nr;
  for (i=1;i<=nrcuv;i++)
  {
    nr=0;
    long long putere=1;
    for (j=0;j<lgcuv;j++)
    {
      nr=nr+(cuvant[i][j]-'a')*putere;
      putere=putere*3;
    }
    v[nr%prim].push_back(nr);
  }
}

void rezolvare()
{
  long long putere=1,nr=0;
  for (long long poz=0;poz<=lgsir-lgcuv+1;poz++)
  {
    if (poz==0)
    {
      for (j=poz;j<poz+lgcuv;j++)
      {
        nr=nr+(sir[j]-'a')*putere;
        putere=putere*3;
      }
      putere=putere/3;
    }
    else nr=(nr-(sir[poz-1]-'a'))/3+(sir[poz+lgcuv-1]-'a')*putere;
    if (caut(nr,nr%prim)) sol++;
  }
  fo<<sol;
}
int main()
{
  citire();
  transformare();
  rezolvare();
  return 0;
}