Pagini recente » Cod sursa (job #1381100) | Cod sursa (job #2420894) | Cod sursa (job #2563127) | Cod sursa (job #254034) | Cod sursa (job #2296412)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
#define mod 11083
vector <unsigned int> v[mod];
unsigned int verificare_candidati(unsigned int nr)
{
unsigned int i,aux,dimensiune;
aux=nr%mod;//aplicam functia modulo
dimensiune=v[aux].size();
for(i=0;i<dimensiune;i++)
{
if(v[aux][i]==nr)//daca il gasim
{
return 1;//returnam 1
}
}
return 0;//returnam 0
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string sir_initial,cuvant;
unsigned int nr,p=1,nr_candidati=0,i;
unsigned int lgcuv,lgsir;
fin>>sir_initial; //citim sirul initial
lgsir=sir_initial.size();
fin>>cuvant;//citim primul cuvant
lgcuv=cuvant.size();
nr=0;
for(i=0;i<lgcuv;i++)
{
nr*=3;
nr+=(cuvant[i]-'a');
}
v[nr%mod].push_back(nr);//introducem codificarea primului cuvant in vector
while(!fin.eof())//introducem urmatoarele cuvinte
{
fin>>cuvant;
nr=0;
for(i=0;i<lgcuv;i++)
{
nr*=3;
nr+=(cuvant[i]-'a');//scadem din caracter 'a', caracterul minim din sistemul limbii makako
}
v[nr%mod].push_back(nr);//adaugam in vector
}
nr=0;
for(i=0;i<lgcuv;i++)
{
p*=3;
nr*=3;
nr+=(sir_initial[i]-'a');
}
p/=3;//inmultim p cu 3 de lgcuv-1 ori
if(verificare_candidati(nr)==1)
{
nr_candidati++;
}
for(i=lgcuv;i<lgsir;i++) //lgcuv pastreaza lungimea unui cuvant normal
{ //lgsir pastreaza lungimea sirului initial
nr-=p*(sir_initial[i-lgcuv]-'a');
nr*=3;//inmultim cu 3, deoarece avem 3 litere in limba Makako a,b,c
nr+=(sir_initial[i]-'a');//
if(verificare_candidati(nr)==1)//verificam daca codificarea unui cuvant este candidat
{
nr_candidati++;//contorizam
}
}
fout<<nr_candidati;
fin.close();
fout.close();
return 0;
}