Pagini recente » Istoria paginii utilizator/dragosuge | Istoria paginii utilizator/georgel19 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2013072)
#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;
}