Pagini recente » Cod sursa (job #30017) | Cod sursa (job #1369173) | Cod sursa (job #1067475) | Cod sursa (job #40161) | Cod sursa (job #1039228)
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#define MOD 666013
using namespace std;
int l,lung,k,u,poz,sol;
unsigned int p3,val,v[50001];
char s[10000001],sir[21];
ifstream fin("abc2.in");
ofstream fout("abc2.out");
unsigned int genereazaHash(char s[],int l)
{
unsigned int h=0;
for(int i=0;i<l;i++)
{
h=h*3+s[i]-'a';
}
return h;
}
void prelucareDictionar()
{
unsigned int h;
fin.getline(sir,21);
lung=strlen(sir);
do
{
v[++k]=genereazaHash(sir,lung);
}while(fin.getline(sir,21));
sort(v+1,v+k+1);
}
void putere3()
{
p3=1;
for(int i=1;i<lung;i++)
{
p3*=3;
}
}
int cauta(unsigned int val)
{
int p=1,u=k,m;
while(p<=u)
{
m=(p+u)/2;
if(v[m]==val)
return 1;
if(v[m]<val)
p=m+1;
else
u=m-1;
}
return 0;
}
int main()
{
fin.getline(s,10000001);
l=strlen(s);
prelucareDictionar();
if(l<lung)
{
fout<<0;
return 0;
}
putere3();
val=genereazaHash(s,lung);
sol+=cauta(val);
for(int i=lung;i<l;i++)
{
val=(val%p3)*3+s[i]-'a';
sol+=cauta(val);
}
fout<<sol;
return 0;
}