Mai intai trebuie sa te autentifici.
Cod sursa(job #1036286)
Utilizator | Data | 19 noiembrie 2013 09:46:05 | |
---|---|---|---|
Problema | Abc2 | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.64 kb |
#include<fstream>
#include<algorithm>
#include<cstring>
#define MOD1 666013
#define MOD2 100021
using namespace std;
int l,lung,k,u,poz,sol,p3,p3m1,p3m2;
char s[10000001],sir[21];
struct code
{
int h1,h2;
};
code h[50001],val;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int cmp(code a,code b)
{
if(a.h1==b.h1)
return a.h2<b.h2;
return a.h1<b.h1;
}
void genereazaHash(char s[],int l,code &h)
{
for(int i=0;i<l;i++)
{
h.h1=(h.h1*3+s[i]-'a')%MOD1;
//h.h2=(h.h2*3+s[i]-'a')%MOD2;
}
}
void prelucareDictionar()
{
fin.getline(sir,21);
lung=strlen(sir);
do
{
genereazaHash(sir,lung,h[++k]);
}while(fin.getline(sir,21));
sort(h+1,h+k+1,cmp);
u=1;;
}
void putere3()
{
p3=1;
for(int i=1;i<lung;i++)
{
p3*=3;
}
p3m1=p3%MOD1;
p3m2=p3%MOD2;
}
int cauta(code val)
{
int st=1,dr=k,m;
while(st<=dr)
{
m=(st+dr)/2;
if(h[m].h1==val.h1)
{
// if(h[m].h2==val.h2)
return 1;
}
if(h[m].h1<val.h1)
{
st=m+1;
}
else
dr=m-1;
}
return 0;
}
int main()
{
fin.getline(s,10000001);
l=strlen(s);
prelucareDictionar();
if(l<lung)
{
fout<<0;
return 0;
}
putere3();
genereazaHash(s,lung,val);
sol+=cauta(val);
for(int i=lung;i<l;i++)
{
val.h1-=((s[i-lung]-'a')*p3m1 )%MOD1;
if(val.h1<0)
val.h1+=MOD1;
val.h1=val.h1*3+s[i]-'a';
while(val.h1>MOD1)
val.h1-=MOD1;
// val.h2-=((s[i-lung]-'a')*p3m2)%MOD2;
// if(val.h2<0)
// val.h2+=MOD2;
// val.h2=val.h2*3+s[i]-'a';
// while(val.h2>MOD2)
// val.h2-=MOD2;
sol+=cauta(val);
}
fout<<sol;
return 0;
}