Cod sursa(job #2008464)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 6 august 2017 16:41:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("abc2.in");
ofstream fo ("abc2.out");
string sir,cuvant[50006];
int i,j,nrcuv,lgcuv,lgsir,sol;
int v[50006];

bool caut(int x,int st,int dr)
{
  int mij=(st+dr)/2;
  if (st>dr) return 0;
  if (v[mij]==x) return 1;
  if (v[mij]>x) return caut(x,st,mij-1);
  if (v[mij]<x) return caut(x,mij+1,dr);
}

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

void transformare()
{
  for (i=1;i<=nrcuv;i++)
  {
    int putere=1;
    for (j=0;j<lgcuv;j++)
    {
      v[i]=v[i]+(cuvant[i][j]-'a')*putere;
      putere=putere*3;
    }
  }
  sort (v+1,v+nrcuv+1);
}

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