Pagini recente » Cod sursa (job #2152085) | Cod sursa (job #522453) | Cod sursa (job #2893821) | Cod sursa (job #1716263) | Cod sursa (job #2008471)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("abc2.in");
ofstream fo ("abc2.out");
string sir,cuvant[50006];
long long i,j,nrcuv,lgcuv,lgsir,sol;
long long 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++)
{
long long 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()
{
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,1,nrcuv)) sol++;
}
fo<<sol;
}
int main()
{
citire();
transformare();
rezolvare();
return 0;
}