Pagini recente » Cod sursa (job #680455) | Cod sursa (job #1528755) | Cod sursa (job #1535009) | Cod sursa (job #2885166) | Cod sursa (job #497576)
Cod sursa(job #497576)
#include <stdio.h>
#include <string.h>
struct hash
{
int nod1,nod2;
hash *link;
}*H[100100];
int nr,n,m,i,sol1,sol2,M1,M2,pow1,pow2;
hash *p;
char string[1000010],s[25];
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(string,1000010,stdin);
n=strlen(string)-1;
if(string[n]=='\n') n--;
fgets(s,25,stdin);
m=strlen(s)-1;
if(s[m]=='\n') m--;
sol1=0;
sol2=0;
M1=100021;
M2=100007;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i]-'a')%M1;
sol2=(sol2*3+s[i]-'a')%M2;
}
nr=0;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr=1;
break;
}
p=p->link;
}
if(nr==0)
{
p=new hash;
p->nod1=sol1;
p->nod2=sol2;
p->link=H[sol1];
H[sol1]=p;
}
while(!feof(stdin))
{
fgets(s,25,stdin);
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+s[i]-'a')%M1;
sol2=(sol2*3+s[i]-'a')%M2;
}
nr=0;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr=1;
break;
}
p=p->link;
}
if(nr==0)
{
p=new hash;
p->nod1=sol1;
p->nod2=sol2;
p->link=H[sol1];
H[sol1]=p;
}
}
nr=0;
sol1=0;
sol2=0;
for(i=0;i<=m;i++)
{
sol1=(sol1*3+string[i]-'a')%M1;
sol2=(sol2*3+string[i]-'a')%M2;
}
pow1=1;
pow2=1;
for(i=1;i<=m;i++)
{
pow1=(pow1*3)%M1;
pow2=(pow2*3)%M2;
}
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr++;
break;
}
p=p->link;
}
/*for(i=m+1;i<=n;i++)
{
sol1=((sol1+M1-(pow1*(string[i-m-1]-'a'))%M1)*3+string[i]-'a')%M1;
sol2=((sol2+M2-(pow2*(string[i-m-1]-'a'))%M2)*3+string[i]-'a')%M2;
p=H[sol1];
while(p!=NULL)
{
if(p->nod1==sol1&&p->nod2==sol2)
{
nr++;
break;
}
p=p->link;
}
}*/
printf("%d\n",nr);
return 0;
}